Codeforces Round #554 Div.2 E - Neko and Flashback

歐拉路徑

神題啊神題！這道題的突破口就是后兩個數組每個元素是一一對應的。

也就是說，對于一個p的排列，b'和c'取得每一個元素的下標在p中都是一樣的。

根據b和c數組的性質可以得出，b[i] <= c[i]。

這也是我們輸出-1的一個判斷方法。

再來看b和c兩個數組，他們是由原數組相鄰兩個數分別取min和max構造出來的，很容易看出b'和c'同一個位置的兩個數一定在原數組中相鄰。

我們可以根據這個相鄰關系建圖，a若與b在原數組中相鄰，就連一條無向邊，那么最后我們要構造的合法數組即為該無向圖的一條歐拉路徑。

因為數據比較大，所以我們要先離散化，再考慮有重邊，我們可以用multiset來存圖，跑過的邊直接刪除就行了。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){int X = 0, w = 0; char ch = 0;while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){A ans = 1;for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;return ans;
}
const int N = 200005;
int n, k, b[N], c[N], p[N], d[N];
vector<int> rd;
multiset<int> g[N];void dfs(int s){for(auto it = g[s].begin(); it != g[s].end(); it = g[s].begin()){int u = *it;g[s].erase(it), g[u].erase(g[u].lower_bound(s));dfs(u);}rd.push_back(s);
}int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();for(int i = 1; i < n; i ++) b[i] = read(), p[++k] = b[i];for(int i = 1; i < n; i ++) c[i] = read(), p[++k] = c[i];for(int i = 1; i < n; i ++){if(b[i] > c[i]){printf("-1\n");return 0;}}sort(p + 1, p + k + 1);k = (int)(unique(p + 1, p + k + 1) - p - 1);for(int i = 1; i < n; i ++){b[i] = (int)(lower_bound(p + 1, p + k + 1, b[i]) - p);c[i] = (int)(lower_bound(p + 1, p + k + 1, c[i]) - p);}for(int i = 1; i < n; i ++){g[b[i]].insert(c[i]), g[c[i]].insert(b[i]);d[b[i]] ++, d[c[i]] ++;}int t = 0;for(int i = 1; i <= k; i ++){if(d[i] & 1) t ++;}if(t != 0 && t != 2){cout << "-1" << endl;return 0;}bool odd = false;for(int i = 1; i <= k; i ++){if(d[i] & 1){odd = true, dfs(i);break;}}if(!odd) dfs(1);if(rd.size() != n) cout << "-1" << endl;else{for(int i = rd.size() - 1; i >= 0; i --){cout << p[rd[i]];if(i != 0) cout << " ";}puts("");}return 0;
}