Submission #710642

#TimeUsernameProblemLanguageResultExecution timeMemory
710642DennisTranBridges (APIO19_bridges)C++17
59 / 100
3018 ms8356 KiB
#pragma GCC optimize("O2") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r) { return l + rnd() % (r - l + 1); } const int MAXN = 1e5 + 5; int nBlock = 505; int N, M, Q, ans[MAXN]; struct Edge{ int u, v, w; } e[2 * MAXN]; struct DSU_roll_back{ vector <int> lab, rnk; stack <int> dsu_save; DSU_roll_back() {}; DSU_roll_back(int _n) { lab.assign(_n + 1, 0); iota(lab.begin(), lab.end(), 0); rnk.assign(_n + 1, 1); } int get(int u) {return lab[u] == u ? u : get(lab[u]);} bool merge(int u, int v) { if ((u = get(u)) == (v = get(v))) return false; if (rnk[u] < rnk[v]) swap(u, v); rnk[u] += rnk[v]; dsu_save.push(v); return lab[v] = u, true; } int data() {return dsu_save.size();} void roll_back(int version) { while (dsu_save.size() > version) { int u = dsu_save.top(); dsu_save.pop(); rnk[lab[u]] -= rnk[u]; lab[u] = u; } } }; bool current_change[MAXN]; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; FOR(i, 1, M) cin >> e[i].u >> e[i].v >> e[i].w; cin >> Q; FOR(i, 1, Q) cin >> e[i + M].u >> e[i + M].v >> e[i + M].w; for (int l = 1; l <= Q; l += nBlock) { int r = min(Q, l + nBlock - 1); vector <int> queries; vector <int> changed; FOR(i, l, r) { if (e[i + M].u == 1) { changed.emplace_back(i); current_change[e[i + M].v] = true; } else { queries.emplace_back(i + M); } } FOR(i, 1, M) { if (current_change[i] == false) { queries.emplace_back(i); } else current_change[i] = false; } sort(ALL(queries), [&] (int x, int y) { if (e[x].w != e[y].w) return e[x].w > e[y].w; return x < y; }); reverse(ALL(changed)); DSU_roll_back ds(N); for (int x : queries) { if (x <= M) { ds.merge(e[x].u, e[x].v); } else { int ver = ds.data(); for (int y : changed) if (y <= x - M) { int id = e[y + M].v; if (current_change[id] == false) { current_change[id] = true; if (e[y + M].w >= e[x].w) { ds.merge(e[id].u, e[id].v); } } } for (int y : changed) if (y > x - M) { int id = e[y + M].v; if (current_change[id] == true) continue; if (e[id].w >= e[x].w) ds.merge(e[id].u, e[id].v); } ans[x - M] = ds.rnk[ds.get(e[x].v)]; ds.roll_back(ver); for (int y : changed) if (y <= x - M) { int id = e[y + M].v; current_change[id] = false; } } } FOR(i, l, r) if (e[i + M].u == 1) { int id = e[i + M].v; e[id].w = e[i + M].w; } } FOR(i, 1, Q) if (e[i + M].u == 2) cout << ans[i] << '\n'; cerr << "Time elapsed: " << TIME << " s.\n"; return (0 ^ 0); }

Compilation message (stderr)

bridges.cpp: In member function 'void DSU_roll_back::roll_back(int)':
bridges.cpp:45:32: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         while (dsu_save.size() > version) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~
#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...