제출 #684220

#제출 시각아이디문제언어결과실행 시간메모리
684220radal다리 (APIO19_bridges)C++17
73 / 100
3083 ms11792 KiB
#include <bits/stdc++.h> //#pragma GCC target("sse,sse2,avx2") //#pragma GCC optimize("unroll-loops,O3") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef pair<ll,ll> pll; constexpr int N = 2e5+10,mod = 1e9+7,sq = 2000; constexpr ll inf = 1e18+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k >>= 1; } return z; } vector<pll> e; int W[N]; int par[N],sz[N],ans[N],lst[N]; bitset<N> mark; vector<pair<int,pll> > Q; vector<int> ve,pors,ch; stack<int> st; int getpar(int v){ if (v == par[v]) return v; return getpar(par[v]); } bool cmp(int i,int j){ return (W[i] > W[j]); } bool cmp2(int i,int j){ return (Q[i].Y.Y > Q[j].Y.Y); } bool mg(int i){ int u = e[i].X,v = e[i].Y; int p1 = getpar(u),p2 = getpar(v); if (p1 == p2) return 0; if (sz[p2] < sz[p1]) swap(p2,p1); par[p1] = p2; sz[p2] += sz[p1]; st.push(p1); return 1; } void undo(){ int u = st.top(); st.pop(); sz[par[u]] -= sz[u]; par[u] = u; } int main(){ ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin >> n >> m; rep(i,0,m){ int u,v,w; cin >> u >> v >> w; e.pb({u,v}); W[i] = w; } int q; cin >> q; rep(i,0,q){ int t,u,v; cin >> t >> u >> v; if (t == 1) u--; Q.pb({t,{u,v}}); } for (int l = 0; l < q; l += sq){ int r = min(l+sq,q); pors.clear(); ve.clear(); ch.clear(); mark.reset(); rep(i,l,r){ if (Q[i].X == 1) mark[Q[i].Y.X] = 1; else pors.pb(i); } rep(i,0,m){ if (!mark[i]) ve.pb(i); else{ ch.pb(i); lst[i] = W[i]; } } sort(all(ve),cmp); sort(all(pors),cmp2); while (!st.empty()) st.pop(); rep(i,1,n+1){ par[i] = i; sz[i] = 1; } int p = 0; for (int i : pors){ for (int j : ch) lst[j] = W[j]; while (p < (int)ve.size() && W[ve[p]] >= Q[i].Y.Y){ mg(ve[p]); p++; } int t = 0; rep(j,l,i){ if (Q[j].X == 2) continue; lst[Q[j].Y.X] = Q[j].Y.Y; } for (int j : ch) if (lst[j] >= Q[i].Y.Y){ t += mg(j); } ans[i] = sz[getpar(Q[i].Y.X)]; while (t--) undo(); } rep(i,l,r) if (Q[i].X == 1) W[Q[i].Y.X] = Q[i].Y.Y; } rep(i,0,q) if (Q[i].X == 2) cout << ans[i] << endl; }
#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...