Submission #542423

#	Time	Username	Problem	Language	Result	Execution time	Memory
542423		codr0	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3059 ms	52588 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];

	void dol(){
		vector<int> vc0;
		for(int i:vc){
			int X=l[i];
			while(1){
				int z=l[i]-1;
				if(z==0) break;
				if(R[z]&&R[z]<=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 z=r[i]+1;
				if(z==n+1) break;
				if(L[z]&&L[z]>=l[i]){
					r[i]=r[z];
				}else break;
			}
			if(r[i]!=X) vc0.pb(i);
		}
		vc=vc0;
	}

	void Main(){
		cin>>n;
		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()){
			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[u]>=v);
			}else ans=(v>=l[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;
	}

Compilation message (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:90:3: note: in expansion of macro 'FOR'
   90 |   FOR(i,1,n) vc.pb(i); dor();
      |   ^~~
long_mansion.cpp:90:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   90 |   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:92:3: note: in expansion of macro 'FOR'
   92 |   FOR(i,1,n) vc.pb(i); dol();
      |   ^~~
long_mansion.cpp:92:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |   FOR(i,1,n) vc.pb(i); dol();
      |                        ^~~

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