oj.uz

Submission #403575

# Submission time Handle Problem Language Result Execution time Memory
403575 2021-05-13T09:41:03 Z errorgorn None (KOI18_family) C++17
17 / 100
 388 ms 59636 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

void rage(){
	cout<<"NO"<<endl;
	rep(x,0,100000) cerr<<"meh"<<endl;
	exit(0);
}

int n,m,k;
int root;
vector<int> al[300005];

int canon[300005]; //canonical index
int idx[300005]; //mapping back to normal index
ii span[300005]; //the span of canonical indexes
set<int> s[300005];  //the l endpoint of canonical index of children


int tkd[300005][20];

int IDX=0;

void dfs1(int i){
	if (i<=k){
		canon[i]=IDX;
		idx[IDX]=i;
		span[i]=ii(canon[i],canon[i]);
		IDX++;
	}
	else{
		span[i]=ii(1e9,-1e9);
		for (auto &it:al[i]){
			int curr=tkd[it][0]=i;
			rep(x,0,20){
				if (curr==-1) break;
				curr=tkd[it][x+1]=tkd[curr][x];
			}
			
			dfs1(it);
			span[i]=ii(
				min(span[i].fi,span[it].fi),
				max(span[i].se,span[it].se)
			);
			s[i].insert(span[it].fi);
		}
		s[i].insert(span[i].se+1);
	}
}

set<ii> r[300005]; //ranges of the canonical indexes
ii span2[300005];

void dfs2(int i){
	if (i<=k){
		r[i].insert(ii(canon[i],canon[i]));
		span2[i]=ii(canon[i],canon[i]);
	}
	else{
		span2[i]=ii(1e9,-1e9);
		for (auto &it:al[i]){
			dfs2(it);
			span2[i]=ii(
				min(span2[i].fi,span2[it].fi),
				max(span2[i].se,span2[it].se)
			);
			
			if (sz(r[it])>sz(r[i])) swap(r[it],r[i]);
			
			for (auto it:r[it]){
				auto temp=r[i].lb(it);
				if (temp!=r[i].end() && (*temp).fi==it.se+1){
					it.se=(*temp).se;
					r[i].erase(temp);
				}
				
				temp=r[i].lb(it);
				if (temp!=r[i].begin() && (*prev(temp)).se+1==it.fi){
					it.fi=(*prev(temp)).fi;
					r[i].erase(prev(temp));
				}
				r[i].insert(it);
			}
		}
	}
	
	//cout<<i<<" "<<span2[i].fi<<" "<<span2[i].se<<endl;
	//for (auto &it:r[i]) cout<<it.fi<<" "<<it.se<<endl;
	
	int curr=idx[span2[i].fi];
	rep(x,20,0){
		int temp=tkd[curr][x];
		if (temp!=-1 && span2[i].fi<=span[temp].fi && span[temp].se<=span2[i].se){
			curr=temp;
		}
	}
	if (tkd[curr][0]!=-1) curr=tkd[curr][0];
	
	for (auto &it:r[i]){
		if (!s[curr].count(it.fi)) rage();
		if (!s[curr].count(it.se+1)) rage();
	}
	
	//cout<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m>>k;
	
	int t;
	rep(x,1,n+1){
		cin>>t;
		
		if (t==0) root=x;
		else al[t].pub(x);
	}
	
	memset(tkd,-1,sizeof(tkd));
	dfs1(root);
	
	//rep(x,1,n+1) cout<<span[x].fi<<" "<<span[x].se<<endl;
	// rep(x,1,n+1){
		// rep(y,0,2) cout<<tkd[x][y]<<" "; cout<<endl;
	// }
	
	rep(x,1,300005) al[x].clear();
	rep(x,1,m+1){
		cin>>t;
		
		if (t==0) root=x;
		else al[t].pub(x);
	}
	
	dfs2(root);
	
	cout<<"YES"<<endl;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58948 KB Output is correct
2 Correct 38 ms 59020 KB Output is correct
3 Correct 352 ms 59504 KB Output is correct
4 Correct 331 ms 59576 KB Output is correct
5 Correct 339 ms 59464 KB Output is correct
6 Correct 388 ms 59428 KB Output is correct
7 Correct 384 ms 59340 KB Output is correct
8 Correct 339 ms 59348 KB Output is correct
9 Correct 360 ms 59636 KB Output is correct
10 Correct 354 ms 59440 KB Output is correct
11 Correct 329 ms 59352 KB Output is correct
12 Correct 331 ms 59436 KB Output is correct
13 Correct 333 ms 59360 KB Output is correct
14 Correct 31 ms 59060 KB Output is correct
15 Correct 34 ms 59024 KB Output is correct
16 Correct 31 ms 59084 KB Output is correct
17 Correct 31 ms 59060 KB Output is correct
18 Correct 30 ms 59032 KB Output is correct
19 Correct 330 ms 59484 KB Output is correct
20 Correct 332 ms 59552 KB Output is correct
21 Correct 328 ms 59460 KB Output is correct
22 Correct 331 ms 59460 KB Output is correct
23 Correct 346 ms 59560 KB Output is correct
24 Correct 335 ms 59460 KB Output is correct
25 Correct 30 ms 58984 KB Output is correct
26 Correct 33 ms 59044 KB Output is correct
27 Correct 35 ms 59044 KB Output is correct
28 Correct 30 ms 59016 KB Output is correct
29 Correct 30 ms 59020 KB Output is correct
30 Correct 30 ms 58972 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58948 KB Output is correct
2 Correct 38 ms 59020 KB Output is correct
3 Correct 352 ms 59504 KB Output is correct
4 Correct 331 ms 59576 KB Output is correct
5 Correct 339 ms 59464 KB Output is correct
6 Correct 388 ms 59428 KB Output is correct
7 Correct 384 ms 59340 KB Output is correct
8 Correct 339 ms 59348 KB Output is correct
9 Correct 360 ms 59636 KB Output is correct
10 Correct 354 ms 59440 KB Output is correct
11 Correct 329 ms 59352 KB Output is correct
12 Correct 331 ms 59436 KB Output is correct
13 Correct 333 ms 59360 KB Output is correct
14 Correct 31 ms 59060 KB Output is correct
15 Correct 34 ms 59024 KB Output is correct
16 Correct 31 ms 59084 KB Output is correct
17 Correct 31 ms 59060 KB Output is correct
18 Correct 30 ms 59032 KB Output is correct
19 Correct 330 ms 59484 KB Output is correct
20 Correct 332 ms 59552 KB Output is correct
21 Correct 328 ms 59460 KB Output is correct
22 Correct 331 ms 59460 KB Output is correct
23 Correct 346 ms 59560 KB Output is correct
24 Correct 335 ms 59460 KB Output is correct
25 Correct 30 ms 58984 KB Output is correct
26 Correct 33 ms 59044 KB Output is correct
27 Correct 35 ms 59044 KB Output is correct
28 Correct 30 ms 59016 KB Output is correct
29 Correct 30 ms 59020 KB Output is correct
30 Correct 30 ms 58972 KB Output is correct
31 Correct 29 ms 58984 KB Output is correct
32 Incorrect 337 ms 59380 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58948 KB Output is correct
2 Correct 38 ms 59020 KB Output is correct
3 Correct 352 ms 59504 KB Output is correct
4 Correct 331 ms 59576 KB Output is correct
5 Correct 339 ms 59464 KB Output is correct
6 Correct 388 ms 59428 KB Output is correct
7 Correct 384 ms 59340 KB Output is correct
8 Correct 339 ms 59348 KB Output is correct
9 Correct 360 ms 59636 KB Output is correct
10 Correct 354 ms 59440 KB Output is correct
11 Correct 329 ms 59352 KB Output is correct
12 Correct 331 ms 59436 KB Output is correct
13 Correct 333 ms 59360 KB Output is correct
14 Correct 31 ms 59060 KB Output is correct
15 Correct 34 ms 59024 KB Output is correct
16 Correct 31 ms 59084 KB Output is correct
17 Correct 31 ms 59060 KB Output is correct
18 Correct 30 ms 59032 KB Output is correct
19 Correct 330 ms 59484 KB Output is correct
20 Correct 332 ms 59552 KB Output is correct
21 Correct 328 ms 59460 KB Output is correct
22 Correct 331 ms 59460 KB Output is correct
23 Correct 346 ms 59560 KB Output is correct
24 Correct 335 ms 59460 KB Output is correct
25 Correct 30 ms 58984 KB Output is correct
26 Correct 33 ms 59044 KB Output is correct
27 Correct 35 ms 59044 KB Output is correct
28 Correct 30 ms 59016 KB Output is correct
29 Correct 30 ms 59020 KB Output is correct
30 Correct 30 ms 58972 KB Output is correct
31 Correct 29 ms 58984 KB Output is correct
32 Incorrect 337 ms 59380 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58948 KB Output is correct
2 Correct 38 ms 59020 KB Output is correct
3 Correct 352 ms 59504 KB Output is correct
4 Correct 331 ms 59576 KB Output is correct
5 Correct 339 ms 59464 KB Output is correct
6 Correct 388 ms 59428 KB Output is correct
7 Correct 384 ms 59340 KB Output is correct
8 Correct 339 ms 59348 KB Output is correct
9 Correct 360 ms 59636 KB Output is correct
10 Correct 354 ms 59440 KB Output is correct
11 Correct 329 ms 59352 KB Output is correct
12 Correct 331 ms 59436 KB Output is correct
13 Correct 333 ms 59360 KB Output is correct
14 Correct 31 ms 59060 KB Output is correct
15 Correct 34 ms 59024 KB Output is correct
16 Correct 31 ms 59084 KB Output is correct
17 Correct 31 ms 59060 KB Output is correct
18 Correct 30 ms 59032 KB Output is correct
19 Correct 330 ms 59484 KB Output is correct
20 Correct 332 ms 59552 KB Output is correct
21 Correct 328 ms 59460 KB Output is correct
22 Correct 331 ms 59460 KB Output is correct
23 Correct 346 ms 59560 KB Output is correct
24 Correct 335 ms 59460 KB Output is correct
25 Correct 30 ms 58984 KB Output is correct
26 Correct 33 ms 59044 KB Output is correct
27 Correct 35 ms 59044 KB Output is correct
28 Correct 30 ms 59016 KB Output is correct
29 Correct 30 ms 59020 KB Output is correct
30 Correct 30 ms 58972 KB Output is correct
31 Correct 29 ms 58984 KB Output is correct
32 Incorrect 337 ms 59380 KB Output isn't correct
33 Halted 0 ms 0 KB -