제출 #982958

#제출 시각아이디문제언어결과실행 시간메모리
982958angella다리 (APIO19_bridges)C++17
59 / 100
3070 ms37432 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 18, SQ = 370; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, m, q, ev[N], eu[N], ew[N], par[N], sz[N], ans[N], mark[N], ch[N]; vector<int> comp, Q[N], evec[N]; vector<int> qvec[N], rbk; int getPar(int v) {return (par[v] == 0 ? v : getPar(par[v]));} void merge(int v, int u) { if(getPar(v) == getPar(u)) return; v=getPar(v), u=getPar(u); if(sz[u] > sz[v]) swap(v,u); par[u] = v, sz[v] += sz[u]; rbk.pb(u); } void rolbak(int tmp) { while(size(rbk) > tmp) { int v = rbk.back(); sz[par[v]] -= sz[v]; par[v] = 0; rbk.pop_back(); } } int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n>>m; for(int i=1; i<=m; i++) { cin>>ev[i]>>eu[i]>>ew[i]; comp.pb(ew[i]); } cin>>q; for(int typ,x,y,i=1; i<=q; i++) { cin>>typ>>x>>y; comp.pb(y); Q[i] = {typ, x, y}; } sort(all(comp)); comp.resize(unique(all(comp))-comp.begin()); for(int i=1; i<=m; i++) { ew[i] = lower_bound(all(comp),ew[i])-comp.begin()+1; } for(int i=1; i<=q; i++) { Q[i][2] = lower_bound(all(comp),Q[i][2])-comp.begin()+1; } fill(sz+1, sz+n+1, 1); for(int i=1; i<=q; i+=SQ) { vector<int> tmp; for(int j=i; j<=q&&j<i+SQ; j++) { if(Q[j][0] == 1) { tmp.pb(j); mark[Q[j][1]] = 1; } else { qvec[Q[j][2]].pb(j); } } for(int j=1; j<=m; j++) { if(mark[j]==0) evec[ew[j]].pb(j); } for(int j=size(comp); j>=1; j--) { for(auto it : evec[j]) { // cout<<" ~ "<<ev[it]<<' '<<eu[it]<<endl; merge(ev[it], eu[it]); } for(auto it : qvec[j]) { for(auto it2 : tmp) { if(it2 <= it) ch[Q[it2][1]]=max(ch[Q[it2][1]],it2); } int rem = size(rbk); for(auto it2 : tmp) { if(ch[Q[it2][1]] >= 0) { if(ch[Q[it2][1]]==0) { if(ew[Q[it2][1]]>=Q[it][2])merge(ev[Q[it2][1]],eu[Q[it2][1]]); } else { if(Q[ch[Q[it2][1]]][2]>=Q[it][2])merge(ev[Q[it2][1]],eu[Q[it2][1]]); } ch[Q[it2][1]] = -1; } } for(auto it2 : tmp) ch[Q[it2][1]] = 0; // fuck(getPar(Q[it][1])); ans[it] = sz[getPar(Q[it][1])]; rolbak(rem); } } for(int j=i; j<=q&&j<i+SQ; j++) { if(Q[j][0] == 1) ew[Q[j][1]] = Q[j][2]; } for(int j=0;j<=max({m,q,(int)size(comp)});j++) { par[j]=mark[j]=0, sz[j]=1; evec[j].clear(); qvec[j].clear(); } rbk.clear(); } for(int i=1; i<=q; i++) { if(ans[i] > 0) 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...