Codeforces 1152E Neko and Flashback 欧拉路径

Neko and Flashback

把a[ i ] - b[ i ] 看成边， 就是求一遍欧拉路径就好了。

注意图不连通的情况。。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
using namespace std;
const int N = (int)2e5 + 7;
int n, a[N], b[N], deg[N];
int hs[N], hs_cnt;
bool ban[N];
vector<PII> G[N];
vector<int> ans;
void dfs(int u) {
while(G[u].size()) {
int v = G[u].back().se;
int id = G[u].back().fi;
G[u].pop_back();
if(!ban[id]) {
ban[id] = true;
dfs(v);
}
}
ans.push_back(hs[u]);
}
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i++) {
scanf("%d", &a[i]);
hs[++hs_cnt] = a[i];
}
for(int i = 1; i < n; i++) {
scanf("%d", &b[i]);
hs[++hs_cnt] = b[i];
}
sort(hs + 1, hs + 1 + hs_cnt);
hs_cnt = unique(hs + 1, hs + 1 + hs_cnt) - hs - 1;
for(int i = 1; i < n; i++) {
a[i] = lower_bound(hs + 1, hs + 1 + hs_cnt, a[i]) - hs;
b[i] = lower_bound(hs + 1, hs + 1 + hs_cnt, b[i]) - hs;
deg[a[i]]++;
deg[b[i]]++;
G[a[i]].push_back(mk(i, b[i]));
G[b[i]].push_back(mk(i, a[i]));
}
for(int i = 1; i < n; i++) {
if(a[i] > b[i]) {
puts("-1");
return 0;
}
}
int be = 1, cnt = 0;
for(int i = 1; i <= hs_cnt; i++) {
if(deg[i] & 1) {
be = i;
cnt++;
}
}
if(cnt != 0 && cnt != 2) puts("-1");
else {
dfs(be);
if(ans.size() != n) return puts("-1"), 0;
for(int i = (int)ans.size() - 1; i >= 0; i--) {
printf("%d%c", ans[i], " n"[i == 0]);
}
}
return 0;
}
/*
*/