Submission #1198698

#TimeUsernameProblemLanguageResultExecution timeMemory
1198698hengliao다리 (APIO19_bridges)C++20
14 / 100
2049 ms30600 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pll pair<ll, ll> #define vll vector<ll> #define pb push_back typedef long long ll; const ll mxN=2e5+5; const ll B=500; struct Edge{ ll u, v, t1, t2, w; bool operator<(const Edge &tar) const{ return w>tar.w; } }; ll n, m, q; pll edges[mxN]; ll w[mxN]; ll pret[mxN]; ll flag[mxN]; ll b[mxN], r[mxN], s[mxN], cw[mxN], ans[mxN]; ll dsu[mxN]; vector<array<ll, 6>> v; vector<array<ll, 4>> roll; ll ceil_div(ll a, ll b){ return (a+b-1)/b; } void init_dsu(){ memset(dsu, -1, sizeof(dsu)); } ll find_set(ll tar){ if(dsu[tar]<0) return tar; return dsu[tar]=find_set(dsu[tar]); } ll find_set2(ll tar){ if(dsu[tar]<0) return tar; return find_set(dsu[tar]); } void unite(ll a, ll b){ ll f=find_set(a); ll s=find_set(b); if(abs(dsu[f]<abs(dsu[s]))) swap(f, s); dsu[f]+=dsu[s]; dsu[s]=f; } void unite2(ll a, ll b){ ll f=find_set2(a); ll s=find_set2(b); if(abs(dsu[f]<abs(dsu[s]))) swap(f, s); roll.pb({f, dsu[f], s, dsu[s]}); dsu[f]+=dsu[s]; dsu[s]=f; } void roll_back(){ // assert(!roll.empty()); dsu[roll.back()[0]]=roll.back()[1]; dsu[roll.back()[2]]=roll.back()[3]; roll.pop_back(); } void solve(){ cin>>n>>m; for(ll i=0;i<m;i++){ cin>>edges[i].F>>edges[i].S>>w[i]; } cin>>q; for(ll i=0;i<q;i++){ cin>>flag[i]; pret[i]=0; if(flag[i]==1){ cin>>b[i]>>r[i]; b[i]--; } else{ cin>>s[i]>>cw[i]; } } for(ll i=0;i<q;i++){ if(flag[i]==1){ ll idx=b[i]; array<ll, 6> cur={1, edges[idx].F, edges[idx].S, pret[idx], i-1, w[idx]}; if(cur[3]<=cur[4]) v.pb(cur); pret[idx]=i; w[idx]=r[i]; } } for(ll i=0;i<m;i++){ array<ll, 6> cur={1, edges[i].F, edges[i].S, pret[i], q, w[i]}; if(cur[3]<=cur[4]) v.pb(cur); } for(ll i=0;i<q;i++){ if(flag[i]==2){ array<ll, 6> cur={2, 0, 0, i, s[i], cw[i]}; v.pb(cur); } } auto compare=[&](array<ll, 6> a, array<ll, 6> b){ if(a[5]!=b[5]) return a[5]>b[5]; return a[0]<b[0]; }; sort(v.begin(), v.end(), compare); // for(auto &it:v){ // for(ll i=0;i<6;i++){ // cout<<it[i]<<' '; // } // cout<<'\n'; // } for(ll bl=0;bl<ceil_div(q, B);bl++){ vector<array<ll, 6>> tep; init_dsu(); ll low=bl*B; ll high=min((bl+1)*B-1, q-1); for(auto &it:v){ if(it[0]==1){ if(it[3]<low && it[4]>high){ if(find_set(it[1])!=find_set(it[2])){ unite(it[1], it[2]); } } else if((it[3]>=low && it[3]<=high) || (it[4]>=low && it[4]<=high)){ tep.pb(it); } } else{ if(it[3]<low || it[3]>high) continue; ll cnt=0; // cout<<"dealing "<<it[3]<<'\n'; for(auto &it2:tep){ if(it2[3]<=it[3] && it2[4]>=it[3]){ if(find_set2(it2[1])!=find_set2(it2[2])){ unite2(it2[1], it2[2]); // cout<<"uniting "<<it2[1]<<' '<<it2[2]<<'\n'; cnt++; } } } ll p=find_set2(it[4]); ans[it[3]]=abs(dsu[p]); while(cnt--){ roll_back(); } } } } for(ll i=0;i<q;i++){ if(flag[i]==2){ cout<<ans[i]<<'\n'; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); 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...