CF1152E Neko and Flashback——欧拉路径-蒲公英云

CF1152E Neko and Flashback——欧拉路径

Bertha 。 2021-12-02 00:14 328阅读 0赞

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

转载于//www.cnblogs.com/dummyummy/p/10770876.html