Submission #1077674

#TimeUsernameProblemLanguageResultExecution timeMemory
1077674BABY_GANGSTERJail (JOI22_jail)C++17
Compilation error
0 ms0 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 } const int N=1e5+2e4+1; int depth[N]; int head[N]; int pos[N]; int tout[N]; vector<int> v2[N]; vector<ib> v[N*8][2]; int heavy[N]; ib a[N]; int sz[N]; int mxz[N]; int c[N*8][2]; int par[N]; void dfs(int x,int y) { sz[x]=1; mxz[x]=0; par[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]; } } } 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); tout[x]=dem; } 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) { 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>=l1&&r<=r1) { v[x][0].pb({node,0}); // cout<<x<<" "<<node<<" "<<0,down // if(x==5) cout<<node,debug return; } int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1,r1,x); if(r1>=mid+1) 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>=l1&&r<=r1) { v[node][1].pb({x,0}); return; } int mid=l+r>>1; if(l1<=mid)upd2(node<<1,l,mid,l1,r1,x); if(r1>=mid+1)upd2(node<<1|1,mid+1,r,l1,r1,x); } void upd_hld(int u, int v, int i,int dd){ while (head[u]!=head[v]){ if (depth[head[u]]<depth[head[v]]) swap(u, v); upd(1, 1, n, pos[head[u]], pos[u], i); u=par[head[u]]; } if (depth[u]>depth[v]) swap(u, v); upd(1, 1, n, pos[u]+dd, pos[v], i); } void upd_hld2(int u, int v, int i,int dd){ while (head[u]!=head[v]){ if (depth[head[u]]<depth[head[v]]) swap(u, v); upd2(1, 1, n, pos[head[u]], pos[u], i); u=par[head[u]]; } if (depth[u]>depth[v]) swap(u, v); if(pos[u]+dd<=pos[v]) upd2(1, 1, n, pos[u]+dd, pos[v], i); } } stt; bool de; bool check(int x,int y) { if(pos[x]<=pos[y]&&tout[x]>=pos[y]) return 1; return 0; } void dfs2(int x,int y) { c[x][y]=1; for(auto f:v[x][y]){ if(c[f.a][f.b ]==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); stt.setup(1,1,n); m=scan(); for(int i=1; i<=m; i++){ a[i].a=scan(),a[i].b=scan(); v[f[pos[a[i].a]]][0].pb({f[pos[a[i].b]],1}); if(check(a[i].a,a[i].b)){ stt.upd_hld(a[i].a,par[a[i].b],f[pos[a[i].a]],1);} else if(check(a[i].b,a[i].a)){ stt.upd_hld(par[a[i].a],a[i].b,f[pos[a[i].a]],1);} else { stt.upd_hld(par[a[i].a],par[a[i].b],f[pos[a[i].a]],0);} if(check(a[i].b,a[i].a)) stt.upd_hld2(a[i].a,a[i].b,f[pos[a[i].a]],1); else stt.upd_hld2(a[i].a,par[a[i].b],f[pos[a[i].a]],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 function 'void des(int, int)':
jail.cpp:114:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  114 |         if(pos[f]==0)
      |         ^~
jail.cpp:116:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  116 |             tout[x]=dem;
      |             ^~~~
jail.cpp: In member function 'void IT::setup(int, int, int)':
jail.cpp:129:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  129 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
jail.cpp:142:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd2(int, int, int, int, int, int)':
jail.cpp:154:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In function 'void phongbeo()':
jail.cpp:203:23: error: 'f' was not declared in this scope
  203 |         v2[i].clear(),f[i]=0,heavy[i]=0,pos[i]=0,head[i]=0,depth[i]=0;
      |                       ^
jail.cpp:214:10: error: 'f' was not declared in this scope
  214 |        v[f[pos[a[i].a]]][0].pb({f[pos[a[i].b]],1});
      |          ^
jail.cpp:228:15: error: 'f' was not declared in this scope
  228 |         if(!c[f[pos[a[i].a]]][0]) dfs2(f[pos[a[i].a]],0);
      |               ^