CF1152E Neko and Flashback--欧拉路径

时间:2024-01-13 22:16:50

RemoteJudge

第一次见到欧拉路径的题

注意到\(b\)和\(c\)的构造方法很特殊,即对于一个位置(经过\(p\)作用后)\(i\),若两个数分别为\(b_i\)和\(c_i\),那么在\(a\)中\(b_i\)与\(c_i\)相邻

其实\(p\)并没有什么用

从每一个\(b_i\)向\(c_i\)连边,那么问题转化为是否存在一条长度为\(n\)的欧拉路径,直接\(dfs\)就行了

几个\(-1\)的情况:

1.存在\(i\),使得\(b_i> c_i\)

2.不存在欧拉路径

3.求出来的路径长度不为\(n\)

上代码:

//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \\| |// `.
// / \\||| : |||// \
// / _||||| -:- |||||- \
// | | \\\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 全是BUG
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set> using namespace std; #define ull unsigned long long
#define pii pair<int, int>
#define uint unsigned int
#define mii map<int, int>
#define lbd lower_bound
#define ubd upper_bound
#define ll long long
#define mp make_pair
#define pb push_back
#define re register
#define il inline #define N 100000 int n, m, tot;
mii id;
multiset<int> to[2*N+5];
int ans[10*N+5], tp, d[2*N+5], cnt, p[10*N+5];
int b[N+5], c[N+5], val[2*N+5]; void dfs(int u) {
for(auto i = to[u].begin(); i != to[u].end(); i = to[u].begin()) {
auto v = *i;
to[u].erase(i), to[v].erase(to[v].lbd(u));
dfs(v);
}
ans[++tp] = u;
} int main() {
scanf("%d", &n);
for(int i = 1; i < n; ++i) {
scanf("%d", &b[i]);
if(!id.count(b[i])) id[b[i]] = ++tot, val[tot] = b[i];
}
for(int i = 1; i < n; ++i) {
scanf("%d", &c[i]);
if(b[i] > c[i]) {
printf("-1\n");
return 0;
}
if(!id.count(c[i])) id[c[i]] = ++tot, val[tot] = c[i];
to[id[c[i]]].insert(id[b[i]]), to[id[b[i]]].insert(id[c[i]]);
d[id[c[i]]]++, d[id[b[i]]]++;
}
for(int i = 1; i <= tot; ++i) if(d[i]&1) p[++cnt] = i;
if(cnt != 0 && cnt != 2) printf("-1\n");
else {
if(cnt == 0) dfs(1);
else dfs(p[1]);
if(tp != n) printf("-1\n");
else {
while(tp) printf("%d ", val[ans[tp--]]);
printf("\n");
}
}
return 0;
}