Submission #166487

#TimeUsernameProblemLanguageResultExecution timeMemory
166487FeederBridges (APIO19_bridges)C++11
59 / 100
3028 ms8140 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; int par[50001], sz[50001], rnk[50001]; int findp(int x){ return x == par[x] ? x : findp(par[x]); } void merge(int x, int y){ x = findp(x), y = findp(y); if(x == y) return; if(rnk[x] < rnk[y]) swap(x, y); par[y] = x; if(rnk[x] == rnk[y]) rnk[x]++; sz[x] += sz[y]; } void split(int x, int y, int w){ if(w > 0) rnk[x]--; else w = -w; par[y] = y; sz[x] = w; } int n, m, a, b, w, q, t, rt, edgea[100001], edgeb[100001], warr[100001], ans[100001]; set<tuple<int, int> > edgelist; vector<tuple<int, int, int> > uvec; // query, bridge, weight vector<tuple<int, int, int> > qvec; // weight, query, island int qcnt = 0; int cbridges[100001]; void findans(int qnum){ //cout << "findans: " << qnum << endl; vector<tuple<int, int, int> > st; vector<int> vec; int qw, qi, qq; tie(qw, qq, qi) = qvec[qnum]; for(int i=int(uvec.size())-1; i>=0; i--){ if(get<0>(uvec[i]) > qq) continue; int bnum = get<1>(uvec[i]); w = get<2>(uvec[i]); if(cbridges[bnum] == 2) continue; cbridges[bnum] = 2; vec.push_back(bnum); if(w < qw) continue; a = edgea[bnum], b = edgeb[bnum]; a = findp(a), b = findp(b); //cout << a << ' ' << b << ' ' << w << endl; if(a == b) continue; if(rnk[a] < rnk[b]) swap(a, b); if(rnk[a] == rnk[b]) st.emplace_back(a, b, sz[a]); else st.emplace_back(a, b, -sz[a]); merge(a, b); } for(auto i:vec) cbridges[i] = 1; ans[qq] = sz[findp(qi)]; for(int i=int(st.size())-1; i>=0; i--){ tie(a, b, w) = st[i]; split(a, b, w); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=1; i<=m; i++){ cin >> edgea[i] >> edgeb[i] >> w; edgelist.insert(make_tuple(-w, i)); warr[i] = w; } cin >> q; fill(ans, ans + q, -1); rt = 500; for(int i=0; i<q; i++){ cin >> t >> a >> b; if(t == 1){ uvec.emplace_back(i, a, b); if(!cbridges[a]){ cbridges[a] = 1; uvec.emplace_back(-1, a, warr[a]); } } else qvec.emplace_back(b, i, a); if(i % rt != rt - 1 && i != q - 1) continue; qcnt = int(qvec.size()) - 1; sort(qvec.begin(), qvec.end()); sort(uvec.begin(), uvec.end()); for(int j=1; j<=n; j++) par[j] = j; fill(sz + 1, sz + n + 1, 1); fill(rnk + 1, rnk + n + 1, 0); for(auto it:edgelist){ tie(w, a) = it; int prew = -w, prea = a; while(qcnt >= 0 && get<0>(qvec[qcnt]) > prew){ findans(qcnt); qcnt--; } if(cbridges[prea]) continue; b = edgeb[prea]; a = edgea[prea]; //cout << "merge: " << a << ' ' << b << endl; merge(a, b); } while(qcnt >= 0){ findans(qcnt); qcnt--; } for(int j=int(uvec.size())-1; j>=0; j--){ b = get<1>(uvec[j]), w = get<2>(uvec[j]); if(cbridges[b] == 0) continue; edgelist.erase(make_tuple(-warr[b], b)); edgelist.insert(make_tuple(-w, b)); warr[b] = w; cbridges[b] = 0; } uvec.clear(); qvec.clear(); } for(int i=0; i<q; i++){ if(ans[i] != -1) cout << ans[i] << '\n'; } }
#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...