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;
}