Submission #948144

#TimeUsernameProblemLanguageResultExecution timeMemory
948144BlagojColors (RMI18_colors)C++17
100 / 100
484 ms90616 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 2e5; vector<int> a(mxn), b(mxn), cntA[mxn], cntB[mxn], ldr(mxn), rnk(mxn); vector<pair<int, int>> edges, sgt[4 * mxn]; struct State { int x, y, xSize, ySize; }; stack<State> s; void clear(int n) { edges.clear(); for (int i = 1; i <= n; i++) { cntA[i].clear(); cntB[i].clear(); } for (int i = 1; i <= 4 * n; i++) sgt[i].clear(); } void update(int k, int l, int r, int i, int j, pair<int, int> x) { if (l > j || r < i) return; if (i <= l && r <= j) { sgt[k].push_back(x); return; } int mid = (l + r) / 2; update(k * 2, l, mid, i, j, x); update(k * 2 + 1, mid + 1, r, i, j, x); } int Find(int x) { if (x == ldr[x]) return x; else return Find(ldr[x]); } void Union(int x, int y) { x = Find(x), y = Find(y); if (x == y) return; if (rnk[x] < rnk[y]) swap(x, y); s.push({x, y, rnk[x], rnk[y]}); ldr[y] = x; rnk[x] += rnk[y]; } void rollback(int sz) { while (s.size() > sz) { State top = s.top(); s.pop(); ldr[top.x] = top.x; ldr[top.y] = top.y; rnk[top.x] = top.xSize; rnk[top.y] = top.ySize; } } bool flag; void solve(int k, int l, int r) { int sz = s.size(); for (auto [f, t] : sgt[k]) Union(f, t); if (l == r) { unordered_set<int> cnt; for (auto x : cntA[l]) cnt.insert(Find(x)); for (auto x : cntB[l]) { if (!cnt.count(Find(x))) flag = 0; } } else { int mid = (l + r) / 2; solve(k * 2, l, mid); solve(k * 2 + 1, mid + 1, r); } rollback(sz); } void testCase() { int n, m; cin >> n >> m; clear(n); for (int i = 1; i <= n; i++) { cin >> a[i]; cntA[a[i]].push_back(i); } for (int i = 1; i <= n; i++) { cin >> b[i]; cntB[b[i]].push_back(i); } for (int i = 0; i < m; i++) { int f, t; cin >> f >> t; edges.push_back({f, t}); } for (int i = 1; i <= n; i++) { if (a[i] < b[i]) { cout << 0 << endl; return; } } for (auto [f, t] : edges) { int mn = max(b[f], b[t]); int mx = min(a[f], a[t]); if (mn <= mx) update(1, 1, n, mn, mx, {f, t}); } flag = 1; solve(1, 1, n); cout << flag << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); for (int i = 1; i < mxn; i++) { ldr[i] = i; rnk[i] = 1; } int t; cin >> t; while (t--) { testCase(); } }

Compilation message (stderr)

colors.cpp: In function 'void rollback(int)':
colors.cpp:55:21: warning: comparison of integer expressions of different signedness: 'std::stack<State>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while (s.size() > sz) {
      |            ~~~~~~~~~^~~~
#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...