Submission #942013

#TimeUsernameProblemLanguageResultExecution timeMemory
942013NK_Colors (RMI18_colors)C++17
100 / 100
381 ms65080 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define sz(x) int(x.size()) #define f first #define s second #define mp make_pair template<class T> using V = vector<T>; using vi = V<int>; using pi = pair<int, int>; using vpi = V<pi>; const int nax = 2e5+5; int e[nax], has[nax]; V<array<int, 4>> his; void reset(int n) { his = {}; for(int i = 0; i < n; i++) e[i] = -1; } int get(int x) { return e[x] < 0 ? x : get(e[x]); } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) { his.pb({-1, -1, -1, -1}); return 0; } if (e[x] > e[y]) swap(x, y); his.pb({x, y, e[x], e[y]}); e[x] += e[y]; e[y] = x; return 1; } void roll(int t) { for(int i = 0; i < t; i++) { auto [x, y, ex, ey] = his.back(); his.pop_back(); if (x == -1) continue; e[x] = ex, e[y] = ey; } } void solve() { int N, M; cin >> N >> M; reset(N); vi A(N); for(auto& x : A) { cin >> x; --x; } vi B(N); for(auto& x : B) { cin >> x; --x; } V<vi> ocA(N), ocB(N); for(int i = 0; i < N; i++) { ocA[A[i]].pb(i); ocB[B[i]].pb(i); } int K = 1; while(K < N) K *= 2; V<vpi> E(2 * K); for(int i = 0; i < M; i++) { int u, v; cin >> u >> v; --u, --v; int l = max(B[u], B[v]), r = min(A[u], A[v]); for(l += K, r += K+1; l < r; l /= 2, r /= 2) { if (l & 1) E[l++].pb(mp(u, v)); if (r & 1) E[--r].pb(mp(u, v)); } } int ans = 1; function<void(int, int, int)> answer = [&](int x, int l, int r) { if (l > min(r, N - 1)) return; // cout << x << " => " << l << " " << r << endl; int amt = sz(E[x]); for(auto& e : E[x]) { // cout << e.f << " " << e.s << endl; unite(e.f, e.s); } if (l == r) { for(auto& u : ocA[l]) has[get(u)] = 1; for(auto& u : ocB[l]) if (!has[get(u)]) ans = 0; for(auto& u : ocA[l]) has[get(u)] = 0; } else { int m = (l + r) / 2; answer(2 * x, l, m); answer(2 * x + 1, m + 1, r); } roll(amt); }; answer(1, 0, K - 1); cout << ans << nl; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while(T--) { solve(); } exit(0-0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...