제출 #543006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543006		codr0	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3076 ms	50784 KiB

long_mansion

// 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();
      |                        ^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75