제출 #199238

#제출 시각아이디문제언어결과실행 시간메모리
199238Alexa2001다리 (APIO19_bridges)C++17
73 / 100
3055 ms20236 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 2e5 + 5, B = 1044; struct Edge { int x, y, c; }; struct Query { int t, x, c; }; int n, m, nq, lim; int last[Nmax], nxt[Nmax], prv[Nmax]; Edge edge[Nmax]; Query q[Nmax]; int ans[Nmax]; vector<int> modif, query[Nmax], when[Nmax]; static void read() { int i; cin >> n >> m; for(i=1; i<=m; ++i) cin >> edge[i].x >> edge[i].y >> edge[i].c; cin >> nq; for(i=1; i<=nq; ++i) cin >> q[i].t >> q[i].x >> q[i].c; for(i=1; i<=nq; ++i) if(q[i].t == 1) { prv[i] = last[q[i].x]; last[q[i].x] = i; } for(i=1; i<=m; ++i) last[i] = 1e9; for(i=nq; i; --i) if(q[i].t == 1) { nxt[i] = last[q[i].x]; last[q[i].x] = i; } for(i=1; i<=m; ++i) last[i] = 0; } static void normalize() { vector<int> all; int i; for(i=1; i<=m; ++i) all.push_back(edge[i].c); for(i=1; i<=nq; ++i) if(q[i].t == 1) all.push_back(q[i].c); sort(all.begin(), all.end()); all.erase( unique(all.begin(), all.end()), all.end() ); lim = all.size(); for(i=1; i<=m; ++i) edge[i].c = lower_bound(all.begin(), all.end(), edge[i].c) - all.begin(); for(i=1; i<=nq; ++i) q[i].c = lower_bound(all.begin(), all.end(), q[i].c) - all.begin(); } struct DisjDataSet { int t[Nmax]; int s[Nmax]; int tip; vector<int> who, old_size; int boss(int x) { int y = x; while(t[y] != y) y = t[y]; if(tip == 1) { int z = y; y = x; while(t[y] != y) { int ny = t[y]; t[y] = z; y = ny; } } return y; } void reset() { int i; tip = -1; for(i=1; i<=n; ++i) t[i] = i, s[i] = 1; } void unite(int x, int y) { x = boss(x); y = boss(y); if(x == y) return; if(s[x] > s[y]) swap(x, y); if(tip == 2) who.push_back(x), old_size.push_back(s[x]); t[x] = y; s[y] += s[x]; } void undo() { int i; for(i=who.size()-1; i>=0; --i) s[t[who[i]]] -= old_size[i], t[who[i]] = who[i]; who.clear(); old_size.clear(); } int get_size(int x) { x = boss(x); return s[x]; } } forest; static void solve(int start) { int i; /// modif.clear(); for(i=0; i<=lim; ++i) when[i].clear(), query[i].clear(); forest.reset(); /// for(i=start; i<start+B && i<=nq; ++i) if(q[i].t == 1) { last[q[i].x] = i; modif.push_back(i); } else query[q[i].c].push_back(i); for(i=1; i<=m; ++i) if(last[i] < start) when[edge[i].c].push_back(i); for(i=lim; i>=0; --i) { /// forest.tip = 1; for(auto &it : when[i]) forest.unite(edge[it].x, edge[it].y); /// forest.tip = 2; for(auto &it : query[i]) { for(auto &j : modif) if( (j < it && nxt[j] > it && q[j].c >= i) || (prv[j] < start && j > it && edge[q[j].x].c >= i) ) forest.unite(edge[q[j].x].x, edge[q[j].x].y); ans[it] = forest.get_size(q[it].x); forest.undo(); } } for(auto &j : modif) edge[q[j].x].c = q[j].c; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); read(); normalize(); int i; for(i=1; i<=nq; i+=B) solve(i); for(i=1; i<=nq; ++i) if(q[i].t == 2) cout << ans[i] << '\n'; 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...