Submission #979819

#TimeUsernameProblemLanguageResultExecution timeMemory
979819peterandvoiCollapse (JOI18_collapse)C++17
100 / 100
1359 ms83572 KiB
#include <bits/stdc++.h> #include "collapse.h" using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const int S = 320; vector<int> simulateCollapse(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) { int Q = int(W.size()), C = int(X.size()); vector<int> ord(Q), res(Q); vector<pair<int, int>> edges; for (int i = 0; i < C; ++i) { if (X[i] > Y[i]) { swap(X[i], Y[i]); } edges.emplace_back(X[i], Y[i]); } sort(edges.begin(), edges.end()); edges.erase(unique(edges.begin(), edges.end()), edges.end()); int m = int(edges.size()); vector<int> idx(C); for (int i = 0; i < C; ++i) { idx[i] = lower_bound(edges.begin(), edges.end(), make_pair(X[i], Y[i])) - edges.begin(); } vector<vector<int>> qry(C); for (int i = 0; i < Q; ++i) { qry[W[i]].emplace_back(i); } iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int i, int j) { return W[i] < W[j]; }); vector<int> lab(n, -1); vector<pair<int, int>> his; int cc = n; auto get = [&](auto get, int u) -> int { return lab[u] < 0 ? u : get(get, lab[u]); }; auto unite = [&](int u, int v, bool rb) { u = get(get, u), v = get(get, v); if (u ^ v) { if (lab[u] > lab[v]) { swap(u, v); } if (rb) { his.emplace_back(v, lab[v]); } lab[u] += lab[v]; lab[v] = u; cc--; } }; auto rollback = [&]() { while (his.size()) { auto [v, sz] = his.back(); his.pop_back(); int u = lab[v]; lab[u] -= sz; lab[v] = sz; cc++; } }; auto reset = [&]() { cc = n; fill(lab.begin(), lab.end(), -1); his.clear(); }; vector<int> inc(m); iota(inc.begin(), inc.end(), 0); auto dec = inc; sort(inc.begin(), inc.end(), [&](int i, int j) { return edges[i].second < edges[j].second; }); sort(dec.begin(), dec.end(), [&](int i, int j) { return edges[i].first > edges[j].first; }); vector<bool> cant(m, false), state(m, false); vector<vector<int>> gL(Q), gR(Q); int time = 0; for (int s = 0; s < C; s += S) { int l = s, r = min(C, s + S) - 1; vector<int> cands; for (int i = l; i <= r; ++i) { cands.emplace_back(idx[i]); } sort(cands.begin(), cands.end()); cands.erase(unique(cands.begin(), cands.end()), cands.end()); for (int id : cands) { cant[id] = true; } vector<int> v; for (int i = l; i <= r; ++i) { state[idx[i]] = 1 - state[idx[i]]; for (int id : qry[i]) { v.emplace_back(id); for (int u : cands) { if (state[u]) { if (edges[u].second <= P[id]) { gL[id].emplace_back(u); } else if (edges[u].first > P[id]) { gR[id].emplace_back(u); } } } } } sort(v.begin(), v.end(), [&](int i, int j) { return P[i] < P[j]; }); reset(); int j = 0; for (int id : v) { while (j < m && edges[inc[j]].second <= P[id]) { int i = inc[j]; if (!cant[i] && state[i]) { unite(edges[i].first, edges[i].second, false); } j++; } for (int k : gL[id]) { unite(edges[k].first, edges[k].second, true); } res[id] += cc - n + P[id] + 1; rollback(); } reverse(v.begin(), v.end()); reset(); j = 0; for (int id : v) { while (j < m && edges[dec[j]].first > P[id]) { int i = dec[j]; if (!cant[i] && state[i]) { unite(edges[i].first, edges[i].second, false); } j++; } for (int k : gR[id]) { unite(edges[k].first, edges[k].second, true); } res[id] += cc - P[id] - 1; rollback(); } for (int id : cands) { cant[id] = false; } } return res; } #ifdef ngu int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif int n, C, Q; cin >> n >> C >> Q; vector<int> T(C), X(C), Y(C); for (int i = 0; i < C; ++i) { cin >> T[i] >> X[i] >> Y[i]; } vector<int> W(Q), P(Q); for (int i = 0; i < Q; ++i) { cin >> W[i] >> P[i]; } auto res = simulateCollapse(n, T, X, Y, W, P); for (int i = 0; i < Q; ++i) { cout << res[i] << " "; } } #endif ngu

Compilation message (stderr)

collapse.cpp:180:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  180 | #endif ngu
      |        ^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:86:9: warning: unused variable 'time' [-Wunused-variable]
   86 |     int time = 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...