Submission #1210634

#TimeUsernameProblemLanguageResultExecution timeMemory
1210634dubabubaBridges (APIO19_bridges)C++17
100 / 100
2768 ms6128 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxn = 1e5 + 10; const int BLOCK_sz = 550; int n, m, q, weight[mxn]; vector<pii> edges(mxn); vector<pii> query(mxn); bool changed[mxn]; int type[mxn]; int ans[mxn]; namespace DSU { int par[mxn]; stack<pair<pii, pii>> hist; static inline int parent(int u) { while(par[u] > 0) { u = par[u]; } return u; } static inline void unite(int u, int v) { u = parent(u); v = parent(v); if(u == v) return; if(par[u] > par[v]) swap(u, v); hist.push(MP(MP(u, par[u]), MP(v, par[v]))); par[u] += par[v]; par[v] = u; } static inline void roll_back(int sz) { while(hist.size() > sz) { int u, pu, v, pv; tie(u, pu) = hist.top().ff; tie(v, pv) = hist.top().ss; par[u] = pu; par[v] = pv; hist.pop(); } } static inline void clear(int n) { memset(par, -1, sizeof(int) * (n + 5)); while(hist.size()) hist.pop(); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++) { cin >> edges[i].ff >> edges[i].ss >> weight[i]; } cin >> q; for(int i = 0; i < q; i++) { cin >> type[i] >> query[i].ff >> query[i].ss; } function<void(int)> connect = [&](int i) { DSU::unite(edges[i].ff, edges[i].ss); }; // i - edge ID for(int L = 0; L < q; L += BLOCK_sz) { int R = min(L + BLOCK_sz, q); for(int i = 1; i <= m; i++) changed[i] = 0; vector<int> ask, upt; for(int i = L; i < R; i++) { int x = query[i].ff; // edge ID or node int w = query[i].ss; if(type[i] == 1) { changed[x] = 1; upt.push_back(x); } else { ask.push_back(i); } } vector<int> UC; for(int i = 1; i <= m; i++) { if(!changed[i]) UC.push_back(i); } sort(ask.begin(), ask.end(), [&](int i, int j) { return query[i].ss > query[j].ss; }); // i, j - query ID sort(UC.begin(), UC.end(), [&](int i, int j) { return weight[i] > weight[j]; }); // i, j - edge ID vector<int> join[BLOCK_sz]; for(int i = L; i < R; i++) { int x = query[i].ff; int w = query[i].ss; if(type[i] == 1) { weight[x] = w; } else { for(int j : upt) { if(weight[j] >= w) join[i - L].push_back(j); } } } DSU::clear(n); int ptr = 0; for(int cur : ask) { // cur - current query ID const int u = query[cur].ff; const int w = query[cur].ss; while(ptr < UC.size()) { int e = UC[ptr]; if(weight[e] < w) break; connect(e); ptr++; } const int snap = DSU::hist.size(); for(int i : join[cur - L]) connect(i); int p = DSU::parent(u); ans[cur] = -DSU::par[p]; DSU::roll_back(snap); // sus } } for(int i = 0; i < q; i++) { if(type[i] == 2) { cout << ans[i] << endl; } } return 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...