Submission #259274

#TimeUsernameProblemLanguageResultExecution timeMemory
259274alishahali1382Bridges (APIO19_bridges)C++14
100 / 100
2961 ms7156 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") //#pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=100010, SQ=600; int n, m, q, u, v, x, y, t, a, b; int E[MAXN][2], W[MAXN], W2[MAXN]; int typ[MAXN], A[MAXN], B[MAXN], ans[MAXN]; int ind[MAXN], ind1[MAXN], ind2[MAXN], m1, m2; int par[MAXN], sz[MAXN], par2[MAXN], sz2[MAXN], comp[MAXN]; int bad[MAXN], vec[MAXN], ted; pii Q[SQ+1]; inline bool cmp(int x, int y){ return W[x]>W[y];} int getpar(int x){ return (par[x]==x?x:par[x]=getpar(par[x]));} inline void join(int x, int y){ x=getpar(x); y=getpar(y); if (x==y) return ; sz[x]+=sz[y]; par[y]=x; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); cin>>n>>m; for (int i=1; i<=m; i++) cin>>E[i][0]>>E[i][1]>>W[i], ind[i]=i; sort(ind+1, ind+m+1, cmp); cin>>q; for (int i=0; i<q; i++) cin>>typ[i]>>A[i]>>B[i]; for (int block=0; block*SQ<q; block++){ for (int i=1; i<=n; i++) par[i]=i, sz[i]=1; int ql=block*SQ, qr=min(q, ql+SQ); ted=0; for (int i=ql; i<qr; i++){ if (typ[i]==1) bad[A[i]]=1; else vec[ted++]=A[i]; } for (int i=1; i<=m; i++) if (bad[i]) vec[ted++]=E[i][0], vec[ted++]=E[i][1]; sort(vec, vec+ted); ted=unique(vec, vec+ted)-vec; int qq=0; for (int i=ql; i<qr; i++) if (typ[i]==2) Q[++qq]={B[i], i}; sort(Q+1, Q+qq+1); m1=m2=0; for (int i=1; i<=m; i++){ if (bad[ind[i]]) ind1[++m1]=ind[i]; else ind2[++m2]=ind[i]; } ind2[m2+1]=0; for (int i=1; i<=m2+1; i++){ int e=ind2[i]; while (qq && Q[qq].first>W[e]){ int id=Q[qq--].second; for (int j=0; j<ted; j++){ int v=comp[vec[j]]=getpar(vec[j]); par2[v]=par[v], sz2[v]=sz[v]; } for (int j=1; j<=m1; j++) W2[ind1[j]]=W[ind1[j]]; for (int j=ql; j<id; j++) if (typ[j]==1) W2[A[j]]=B[j]; for (int j=1; j<=m1; j++) if (W2[ind1[j]]>=B[id]) join(comp[E[ind1[j]][0]], comp[E[ind1[j]][1]]); ans[id]=sz[getpar(comp[A[id]])]; for (int j=0; j<ted; j++){ int v=comp[vec[j]]; par[v]=par2[v], sz[v]=sz2[v]; } } join(E[e][0], E[e][1]); } for (int i=ql; i<qr; i++) if (typ[i]==1) W[A[i]]=B[i]; sort(ind1+1, ind1+m1+1, cmp); merge(ind1+1, ind1+m1+1, ind2+1, ind2+m2+1, ind+1, cmp); for (int i=ql; i<qr; i++) if (typ[i]==1) bad[A[i]]=0; } for (int i=0; i<q; i++) if (typ[i]==2) cout<<ans[i]<<"\n"; return 0; } /* 3 4 1 2 5 2 3 2 3 1 4 2 3 8 1 2 1 5 3 4 1 2 5 2 3 2 3 1 4 2 3 8 2 1 4 1 2 2 5 3 4 1 2 5 2 3 2 3 1 4 2 3 8 2 1 4 1 2 2 5 */
#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...