oj.uz

Submission #543005

# Submission time Handle Problem Language Result Execution time Memory
543005 2022-03-28T19:48:58 Z codr0 Long Mansion (JOI17_long_mansion) C++14
25 / 100
 3000 ms 60844 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=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;
	}

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12824 KB Output is correct
2 Correct 10 ms 12884 KB Output is correct
3 Correct 11 ms 13012 KB Output is correct
4 Correct 9 ms 12756 KB Output is correct
5 Correct 9 ms 12756 KB Output is correct
6 Correct 9 ms 12884 KB Output is correct
7 Correct 22 ms 12756 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12824 KB Output is correct
2 Correct 10 ms 12884 KB Output is correct
3 Correct 11 ms 13012 KB Output is correct
4 Correct 9 ms 12756 KB Output is correct
5 Correct 9 ms 12756 KB Output is correct
6 Correct 9 ms 12884 KB Output is correct
7 Correct 22 ms 12756 KB Output is correct
8 Correct 132 ms 18548 KB Output is correct
9 Correct 91 ms 18576 KB Output is correct
10 Correct 108 ms 19100 KB Output is correct
11 Correct 96 ms 19452 KB Output is correct
12 Correct 93 ms 18196 KB Output is correct
13 Correct 101 ms 18800 KB Output is correct
14 Correct 102 ms 18792 KB Output is correct
15 Correct 95 ms 18780 KB Output is correct
16 Correct 95 ms 18672 KB Output is correct
17 Correct 96 ms 18800 KB Output is correct
18 Correct 105 ms 18836 KB Output is correct
19 Correct 93 ms 18804 KB Output is correct
20 Correct 110 ms 18784 KB Output is correct
21 Correct 98 ms 18556 KB Output is correct
22 Correct 95 ms 18764 KB Output is correct
23 Correct 108 ms 18512 KB Output is correct
24 Correct 121 ms 18556 KB Output is correct
25 Correct 104 ms 18636 KB Output is correct
26 Correct 116 ms 18536 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 29420 KB Output is correct
2 Correct 167 ms 29376 KB Output is correct
3 Correct 168 ms 28984 KB Output is correct
4 Correct 170 ms 29432 KB Output is correct
5 Correct 171 ms 29264 KB Output is correct
6 Correct 159 ms 28132 KB Output is correct
7 Correct 143 ms 27876 KB Output is correct
8 Correct 150 ms 27780 KB Output is correct
9 Correct 148 ms 27748 KB Output is correct
10 Correct 153 ms 27728 KB Output is correct
11 Correct 144 ms 27812 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12824 KB Output is correct
2 Correct 10 ms 12884 KB Output is correct
3 Correct 11 ms 13012 KB Output is correct
4 Correct 9 ms 12756 KB Output is correct
5 Correct 9 ms 12756 KB Output is correct
6 Correct 9 ms 12884 KB Output is correct
7 Correct 22 ms 12756 KB Output is correct
8 Correct 132 ms 18548 KB Output is correct
9 Correct 91 ms 18576 KB Output is correct
10 Correct 108 ms 19100 KB Output is correct
11 Correct 96 ms 19452 KB Output is correct
12 Correct 93 ms 18196 KB Output is correct
13 Correct 101 ms 18800 KB Output is correct
14 Correct 102 ms 18792 KB Output is correct
15 Correct 95 ms 18780 KB Output is correct
16 Correct 95 ms 18672 KB Output is correct
17 Correct 96 ms 18800 KB Output is correct
18 Correct 105 ms 18836 KB Output is correct
19 Correct 93 ms 18804 KB Output is correct
20 Correct 110 ms 18784 KB Output is correct
21 Correct 98 ms 18556 KB Output is correct
22 Correct 95 ms 18764 KB Output is correct
23 Correct 108 ms 18512 KB Output is correct
24 Correct 121 ms 18556 KB Output is correct
25 Correct 104 ms 18636 KB Output is correct
26 Correct 116 ms 18536 KB Output is correct
27 Correct 176 ms 29420 KB Output is correct
28 Correct 167 ms 29376 KB Output is correct
29 Correct 168 ms 28984 KB Output is correct
30 Correct 170 ms 29432 KB Output is correct
31 Correct 171 ms 29264 KB Output is correct
32 Correct 159 ms 28132 KB Output is correct
33 Correct 143 ms 27876 KB Output is correct
34 Correct 150 ms 27780 KB Output is correct
35 Correct 148 ms 27748 KB Output is correct
36 Correct 153 ms 27728 KB Output is correct
37 Correct 144 ms 27812 KB Output is correct
38 Correct 303 ms 54012 KB Output is correct
39 Correct 291 ms 60844 KB Output is correct
40 Correct 239 ms 45924 KB Output is correct
41 Correct 291 ms 59932 KB Output is correct
42 Correct 156 ms 29096 KB Output is correct
43 Correct 154 ms 29060 KB Output is correct
44 Correct 208 ms 38964 KB Output is correct
45 Correct 214 ms 39124 KB Output is correct
46 Correct 213 ms 39436 KB Output is correct
47 Correct 155 ms 29308 KB Output is correct
48 Correct 149 ms 28864 KB Output is correct
49 Correct 209 ms 38820 KB Output is correct
50 Correct 199 ms 38952 KB Output is correct
51 Correct 210 ms 39852 KB Output is correct
52 Execution timed out 3068 ms 30156 KB Time limit exceeded
53 Halted 0 ms 0 KB -