Submission #132240

#TimeUsernameProblemLanguageResultExecution timeMemory
132240MvCBridges (APIO19_bridges)C++11
43 / 100
1193 ms60308 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include<bits/stdc++.h> //#include "job.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=1e5+50; const int mmax=1e3+50; const int mod=1e9+7; using namespace std; using namespace __gnu_pbds; typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set; int rs,x,y,z,nr,vz[mmax],q,i,t,n,m,vl[nmax],st[4*nmax],l,r,mid,lb,rb,p[nmax],sz[nmax],ans[nmax],j,w[nmax],par[nmax]; vector<pair<pair<int,int>,int> >e; vector<pair<int,pair<int,int> > >ne,qr; vector<int>a[nmax]; order_set s[nmax]; pair<int,int>pa; void dfs(int x,int z) { vz[x]=1; nr++; for(int i=0;i<a[x].size();i++) { int y=a[x][i],u=x^e[y].fr.fr^e[y].fr.sc; if(vz[u] || e[y].sc<z)continue; dfs(u,z); } } void upd(int nod,int l,int r,int p) { if(l==r) { st[nod]=vl[l]; return; } int mid=(l+r)/2; if(p<=mid)upd(2*nod,l,mid,p); else upd(2*nod+1,mid+1,r,p); st[nod]=min(st[2*nod],st[2*nod+1]); } int qry(int nod,int l,int r,int tl,int tr) { if(tr<l || tl>r)return inf; if(tl<=l && r<=tr)return st[nod]; int mid=(l+r)/2; return min(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr)); } int fnd(int x) { if(p[x]==x)return x; return p[x]=fnd(p[x]); } void uni(int x,int y) { x=fnd(x); y=fnd(y); if(x!=y) { if(sz[x]<sz[y])swap(x,y); p[y]=x; sz[x]+=sz[y]; } } void dfs1(int x,int pr,int z) { w[x]=z; par[x]=pr; for(int i=0;i<a[x].size();i++) { int y=a[x][i],u=x^e[y].fr.fr^e[y].fr.sc; if(u==pr)continue; dfs1(u,x,e[y].sc); } } void ad(int x) { int y=x,mn=inf; while(x) { s[x].in(mkp(mn,y)); mn=min(mn,w[x]); x=par[x]; } } void re(int x) { int y=x,mn=inf; while(x) { if(s[x].fd(mkp(mn,y))!=s[x].end())s[x].er(s[x].fd(mkp(mn,y))); mn=min(mn,w[x]); x=par[x]; } } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; for(i=1;i<=4*n;i++)st[i]=inf; for(i=1;i<=m;i++) { cin>>x>>y>>z; a[x].pb(i-1); a[y].pb(i-1); e.pb(mkp(mkp(x,y),z)); vl[x]=z; upd(1,1,n,x); } for(i=1;i<=15;i++)if((1<<i)==n+1)break; cin>>q; if((1<<i)==n+1 && m==n-1) { dfs1(1,0,0); for(i=2;i<=n;i++) { ad(i); } while(q--) { cin>>t>>x>>z; if(t==1) { x--; e[x].sc=z; if(e[x].fr.fr==par[e[x].fr.sc])y=e[x].fr.sc; else y=e[x].fr.fr; re(y); w[y]=z; ad(y); } else { while(x) { if(w[x]<z)break; x=par[x]; } z--; if(s[x].upper_bound(mkp(z,1e6))==s[x].end())rs=1; else { pa=*s[x].upper_bound(mkp(z,1e6)); rs=(int)s[x].size()-s[x].order_of_key(pa)+1; } cout<<rs<<'\n'; } } } else if(n<=1000 && m<=1000 && q<=10000) { while(q--) { cin>>t>>x>>z; if(t==1) { x--; e[x].sc=z; } else { memset(vz,0,sizeof(vz)); nr=0; dfs(x,z); cout<<nr<<'\n'; } } return 0; } else if(m==n-1) { while(q--) { cin>>t>>x>>z; if(t==1) { x--; e[x].sc=z; vl[e[x].fr.fr]=z; upd(1,1,n,e[x].fr.fr); } else { l=1,r=x-1,lb=-1; while(l<=r) { mid=(l+r)/2; if(qry(1,1,n,mid,x-1)>=z)lb=mid,r=mid-1; else l=mid+1; } l=x,r=n-1,rb=-1; while(l<=r) { mid=(l+r)/2; if(qry(1,1,n,x,mid)>=z)rb=mid,l=mid+1; else r=mid-1; } if(lb==-1 && rb==-1)cout<<1<<'\n'; else if(lb==-1)cout<<rb+1-x+1<<'\n'; else if(rb==-1)cout<<x-lb+1<<'\n'; else cout<<rb+1-lb+1<<'\n'; } } } else { for(i=1;i<=n;i++) { p[i]=i; sz[i]=1; } for(i=0;i<m;i++) { ne.pb(mkp(e[i].sc,mkp(e[i].fr.fr,e[i].fr.sc))); } sort(ne.begin(),ne.end()); reverse(ne.begin(),ne.end()); for(i=1;i<=q;i++) { cin>>t>>x>>z; qr.pb(mkp(z,mkp(x,i))); } sort(qr.begin(),qr.end()); reverse(qr.begin(),qr.end()); for(i=0;i<q;i++) { for(;j<m;j++) { if(ne[j].fr<qr[i].fr)break; uni(ne[j].sc.fr,ne[j].sc.sc); } ans[qr[i].sc.sc]=sz[fnd(qr[i].sc.fr)]; } for(i=1;i<=q;i++)cout<<ans[i]<<'\n'; } return 0; }

Compilation message (stderr)

bridges.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
bridges.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
bridges.cpp: In function 'void dfs1(int, int, int)':
bridges.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
#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...