oj.uz

Submission #542422

# Submission time Handle Problem Language Result Execution time Memory
542422 2022-03-26T16:44:26 Z codr0 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 95 ms 7188 KB 
// 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=5e3+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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 9 ms 584 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 9 ms 584 KB Output is correct
8 Correct 85 ms 6532 KB Output is correct
9 Correct 90 ms 6400 KB Output is correct
10 Correct 90 ms 6768 KB Output is correct
11 Correct 94 ms 7188 KB Output is correct
12 Correct 88 ms 6084 KB Output is correct
13 Correct 87 ms 6580 KB Output is correct
14 Correct 86 ms 6704 KB Output is correct
15 Correct 87 ms 6648 KB Output is correct
16 Correct 84 ms 6460 KB Output is correct
17 Correct 86 ms 6612 KB Output is correct
18 Correct 86 ms 6656 KB Output is correct
19 Correct 88 ms 6704 KB Output is correct
20 Correct 85 ms 6676 KB Output is correct
21 Correct 86 ms 6476 KB Output is correct
22 Correct 85 ms 6480 KB Output is correct
23 Correct 95 ms 6424 KB Output is correct
24 Correct 88 ms 6420 KB Output is correct
25 Correct 92 ms 6348 KB Output is correct
26 Correct 88 ms 6512 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2304 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 656 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 9 ms 584 KB Output is correct
8 Correct 85 ms 6532 KB Output is correct
9 Correct 90 ms 6400 KB Output is correct
10 Correct 90 ms 6768 KB Output is correct
11 Correct 94 ms 7188 KB Output is correct
12 Correct 88 ms 6084 KB Output is correct
13 Correct 87 ms 6580 KB Output is correct
14 Correct 86 ms 6704 KB Output is correct
15 Correct 87 ms 6648 KB Output is correct
16 Correct 84 ms 6460 KB Output is correct
17 Correct 86 ms 6612 KB Output is correct
18 Correct 86 ms 6656 KB Output is correct
19 Correct 88 ms 6704 KB Output is correct
20 Correct 85 ms 6676 KB Output is correct
21 Correct 86 ms 6476 KB Output is correct
22 Correct 85 ms 6480 KB Output is correct
23 Correct 95 ms 6424 KB Output is correct
24 Correct 88 ms 6420 KB Output is correct
25 Correct 92 ms 6348 KB Output is correct
26 Correct 88 ms 6512 KB Output is correct
27 Runtime error 9 ms 2304 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -