Submission #403582

#	Time	Username	Problem	Language	Result	Execution time	Memory
403582		errorgorn	족보 (KOI18_family)	C++17	100 / 100	662 ms	134384 KiB

family

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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;
	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;
		}
	}
	curr=tkd[curr][0];
	//cout<<curr<<" "<<span2[curr].fi<<" "<<span2[curr].se<<endl;
	//cout<<endl;
	
	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 / 17
• Subtask 2: 27 / 27
• Subtask 3: 15 / 15
• Subtask 4: 41 / 41