Submission #1077501

#TimeUsernameProblemLanguageResultExecution timeMemory
1077501modwweJail (JOI22_jail)C++17
49 / 100
1449 ms133460 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include<bits/stdc++.h> //#define int long long //#define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".ans","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void phongbeo(); const int inf=1e9; const int mod2=1e9+7; const int mod1=998244353; struct icd { long double a; int b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c,d,e; }; int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid; int i,s10,s12; int kk; int el=29; #define getchar_unlocked getchar inline int scan(){ char c = getchar_unlocked(); int x = 0; while(c<'0'||c>'9'){ c=getchar_unlocked(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+c-'0'; c=getchar_unlocked(); } return x; } main() { #ifndef ONLINE_JUDGE //fin(task),fou(task); #endif NHP /// cin>>s1; int xx=scan(); // modwwe while(xx--) phongbeo(),down //checktime } int st[17][120007]; int depth[120007]; int head[120007]; int pos[120007]; vector<int> v2[120007]; vector<ib> v[480007][2]; int heavy[120007]; ib a[120007]; int f[120007]; int sz[120007]; int mxz[120007]; int c[480007][2]; void dfs(int x,int y) { sz[x]=1; mxz[x]=0; st[0][x]=y; depth[x]=depth[y]+1; for(auto f:v2[x]) { if(f!=y) { dfs(f,x); sz[x]+=sz[f]; if(sz[f]>sz[x]) heavy[x]=f,mxz[x]=sz[f]; } } } int lca2(int x,int y) { if(depth[x]<depth[y]) swap(x,y); int ss=depth[x]-depth[y]-1; if(ss>=0) for(int j=0; j<17; ++j) if(bit(ss,j)) x=st[j][x]; if(st[0][x]==y) return x; if(ss!=-1) x=st[0][x]; for(int j=16; j>=0; --j) if(st[j][x]!=st[j][y]) x=st[j][x],y=st[j][y]; return x; } int lca(int x,int y) { if(depth[x]<depth[y]) swap(x,y); int ss=depth[x]-depth[y]; for(int j=0; j<17; ++j) if(bit(ss,j)) x=st[j][x]; if(x==y) return x; for(int j=16; j>=0; --j) if(st[j][x]!=st[j][y]) x=st[j][x],y=st[j][y]; return st[0][x]; } void des(int x,int y) { head[x]=y; pos[x]=++dem; if(heavy[x]!=0) des(heavy[x],y); for(auto f:v2[x]) if(pos[f]==0) des(f,f); } struct IT { void setup(int node,int l,int r) { // cout<<node<<" "<<l<<" "<<r,debug if(node!=1)v[node>>1][0].pb({node,0}); if(node!=1) v[node][1].pb({node>>1,1}); if(l==r) { f[l]=node; return; } int mid=l+r>>1; setup(node<<1,l,mid); setup(node<<1|1,mid+1,r); } void upd(int node,int l,int r,int l1,int r1,int x) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { v[x][0].pb({node,0}); // if(x==5) cout<<node,debug return; } int mid=l+r>>1; upd(node<<1,l,mid,l1,r1,x); upd(node<<1|1,mid+1,r,l1,r1,x); } void upd2(int node,int l,int r,int l1,int r1,int x) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { v[node][1].pb({x,0}); ///if(node==5) cout<<x<<" "<<l1<<" "<<r1<<" fadfdafafa",debug return; } int mid=l+r>>1; upd2(node<<1,l,mid,l1,r1,x); upd2(node<<1|1,mid+1,r,l1,r1,x); } void hld(int x,int y,int z) { if(pos[x]<pos[y]) return; if(pos[head[x]]<=pos[y]) upd(1,1,n,pos[y],pos[x],z); else upd(1,1,n,pos[head[x]],pos[x],z),hld(st[0][head[x]],y,z); } void hld2(int x,int y,int z) { if(pos[x]<pos[y]) return; if(pos[head[x]]<=pos[y]) upd2(1,1,n,pos[y],pos[x],z); else upd2(1,1,n,pos[head[x]],pos[x],z),hld2(st[0][head[x]],y,z); } void upd_hld(int x,int y) { s2=lca(x,y); s3=lca2(s2,y); hld(st[0][x],s2,f[pos[x]]); hld(y,s3,f[pos[x]]); if(s2==y)s2=lca2(x,s2); hld2(x,s2,f[pos[x]]); hld2(st[0][y],s3,f[pos[x]]); } } stt; bool de; void dfs2(int x,int y) { c[x][y]=1; for(auto f:v[x][y]){ if(f.b==0&&c[f.a][0]==1){de=1; return;} if(c[f.a][f.b]) continue; dfs2(f.a,f.b); if(de)return; } c[x][y]=2; } void phongbeo() { n=scan(); /// cach 1 de=0; dem=0; for(int i=1; i<=n; i++) v2[i].clear(),f[i]=0,heavy[i]=0,pos[i]=0,head[i]=0,depth[i]=0; for(int i=1; i<=n*4; i++) v[i][0].clear(),v[i][1].clear(),c[i][0]=c[i][1]=0; for(int i=1; i<n; i++) l=scan(),r=scan(),v2[l].pb(r),v2[r].pb(l); dfs(1,0); des(1,0); for(int i=1; i<17; i++) for(int j=1; j<=n; j++) st[i][j]=st[i-1][st[i-1][j]]; stt.setup(1,1,n); m=scan(); if(n>=120000)assert(0); for(int i=1; i<=m; i++) a[i].a=scan(),a[i].b=scan(),stt.upd_hld(a[i].a,a[i].b),v[f[pos[a[i].a]]][0].pb({f[pos[a[i].b]],1}); dem=0; for(int i=1; i<=m; i++) { if(!c[f[pos[a[i].a]]][0]) dfs2(f[pos[a[i].a]],0); if(de)break; } if(de) cout<<"No"; else cout<<"Yes"; }

Compilation message (stderr)

jail.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~
jail.cpp: In member function 'void IT::setup(int, int, int)':
jail.cpp:156:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
jail.cpp:169:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd2(int, int, int, int, int, int)':
jail.cpp:183:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  183 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd_hld(int, int)':
jail.cpp:205:1: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  205 | if(s2==y)s2=lca2(x,s2);
      | ^~
jail.cpp:206:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  206 |          hld2(x,s2,f[pos[x]]);
      |          ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...