제출 #166507

#제출 시각아이디문제언어결과실행 시간메모리
166507Feeder다리 (APIO19_bridges)C++11
73 / 100
3031 ms9092 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]; } int edgea[100001], edgeb[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){ vector<tuple<int, int, int> > st; vector<int> vec; int qw, qi, qq; tie(qw, qq, qi) = qvec[qnum]; int aa, bb, ww; for(int i=int(uvec.size())-1; i>=0; i--){ if(get<0>(uvec[i]) > qq) continue; int bnum = get<1>(uvec[i]); ww = get<2>(uvec[i]); if(cbridges[bnum] == 2) continue; cbridges[bnum] = 2; vec.push_back(bnum); if(ww < qw) continue; aa = edgea[bnum], bb = edgeb[bnum]; aa = findp(aa), bb = findp(bb); if(aa == bb) continue; if(rnk[aa] < rnk[bb]) swap(aa, bb); if(rnk[aa] == rnk[bb]){ st.emplace_back(aa, bb, sz[aa]); rnk[aa]++; } else st.emplace_back(aa, bb, -sz[aa]); par[bb] = aa; sz[aa] += sz[bb]; } for(auto i:vec) cbridges[i] = 1; ans[qq] = sz[findp(qi)]; for(int i=int(st.size())-1; i>=0; i--){ tie(aa, bb, ww) = st[i]; if(ww > 0) rnk[aa]--; else ww = -ww; par[bb] = bb; sz[aa] = ww; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m, a, b, w, q, t, warr[100001], rt = 650; cin >> n >> m; for(int i=1; i<=m; i++){ cin >> edgea[i] >> edgeb[i] >> warr[i]; edgelist.insert(make_tuple(-warr[i], i)); } cin >> q; int tarr[100001], aarr[100001], barr[100001]; for(int i=0; i<q; i++) cin >> tarr[i] >> aarr[i] >> barr[i]; for(int i=0; i<q; i++){ t = tarr[i], a = aarr[i], b = barr[i]; 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; w = -w; while(qcnt >= 0 && get<0>(qvec[qcnt]) > w) findans(qcnt--); if(cbridges[a]) continue; merge(edgea[a], edgeb[a]); } while(qcnt >= 0) findans(qcnt--); for(int j=int(uvec.size())-1; j>=0; j--){ tie(qcnt, b, w) = uvec[j]; if(qcnt < 0) break; 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]) 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...