제출 #543006

#제출 시각아이디문제언어결과실행 시간메모리
543006codr0Long Mansion (JOI17_long_mansion)C++14
25 / 100
3076 ms50784 KiB
// Code by Parsa Eslami #include <bits/stdc++.h> #define pii pair<int,int> #define bit(i,j) ((j>>i)&1) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORR(i,a,b) for(int i=a;i>=b;i--) #define S second #define F first #define pb push_back #define SZ(x) (int)x.size() #define all(x) x.begin(),x.end() #define err(x) cout<<#x<<": "<<x<<'\n'; using namespace std; const int N=5e5+4; vector<int> vc; int X[N]; int n; int L[N],R[N]; int l[N],r[N]; int pr[N],nxt[N]; int dsu[N]; int to[N]; int parent(int v){ if(dsu[v]<0) return v; return (dsu[v]=parent(dsu[v])); } void join(int a,int b){ int u=a; int v=b; u=parent(u); v=parent(v); //if(u==v) return; if(dsu[u]<dsu[v]) swap(u,v); dsu[v]+=dsu[u]; dsu[u]=v; to[v]=b; pr[b]=pr[a]; } void dol(){ vector<int> vc0; for(int i:vc){ int X=l[i]; while(1){ int Y=to[parent(l[i])]; int z=pr[Y]; if(z==0) break; if(R[z]&&R[z]<=to[parent(r[i])]){ l[i]=l[z]; }else break; } if(l[i]!=X) vc0.pb(i); } vc=vc0; } void dor(){ vector<int> vc0; FORR(j,SZ(vc)-1,0){ int i=vc[j]; int X=r[i]; while(1){ int Y=to[parent(r[i])]; int z=nxt[Y]; if(z==n+1) break; if(L[z]&&L[z]>=to[parent(l[i])]){ r[i]=r[z]; }else break; } if(r[i]!=X) vc0.pb(i); } vc=vc0; reverse(all(vc)); } void Main(){ cin>>n; FOR(i,1,n) dsu[i]=-1,to[i]=i; FOR(i,1,n) nxt[i]=i+1,pr[i]=i-1; int C[n+1]={}; FOR(i,1,n-1) cin>>C[i]; vector<int> B[N]; FOR(i,1,n){ int sz; cin>>sz; FOR(j,1,sz){ int x0; cin>>x0; B[i].pb(x0); } } FOR(i,1,n){ if(i!=1&&X[C[i-1]]){ L[i]=X[C[i-1]]; } FOR(j,0,SZ(B[i])-1){ X[B[i][j]]=i; } } FOR(i,1,n){ FOR(j,0,SZ(B[i])-1){ X[B[i][j]]=0; } } FORR(i,n,1){ if(i!=n&&X[C[i]]){ R[i]=X[C[i]]; } FOR(j,0,SZ(B[i])-1){ X[B[i][j]]=i; } } FOR(i,1,n) l[i]=r[i]=i; FOR(i,1,n) vc.pb(i); dor(); vc.clear(); FOR(i,1,n) vc.pb(i); dol(); while(!vc.empty()){ bool is[N]={}; for(int u0:vc) is[u0]=1; FOR(i,0,SZ(vc)-2){ if(to[parent(r[vc[i]])]>=vc[i+1]&&to[parent(l[vc[i+1]])]<=vc[i]){ is[vc[i]]=0;; join(vc[i],vc[i+1]); } i++; } vc.clear(); FOR(i,1,n) if(is[i]) vc.pb(i); dor(); if(vc.empty()) break; dol(); } int q; cin>>q; while(q--){ int u,v; cin>>u>>v; bool ans; if(u<v){ ans=(r[to[parent(u)]]>=v); }else ans=(v>=l[to[parent(u)]]); cout<<(ans?"YES\n":"NO\n"); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T=1; while(T--) Main(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In function 'void Main()':
long_mansion.cpp:6:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
      |                    ^~~
long_mansion.cpp:114:3: note: in expansion of macro 'FOR'
  114 |   FOR(i,1,n) vc.pb(i); dor();
      |   ^~~
long_mansion.cpp:114:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  114 |   FOR(i,1,n) vc.pb(i); dor();
      |                        ^~~
long_mansion.cpp:6:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
      |                    ^~~
long_mansion.cpp:116:3: note: in expansion of macro 'FOR'
  116 |   FOR(i,1,n) vc.pb(i); dol();
      |   ^~~
long_mansion.cpp:116:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  116 |   FOR(i,1,n) vc.pb(i); dol();
      |                        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...