Submission #131899

#	Time	Username	Problem	Language	Result	Execution time	Memory
131899		dndhk	족보 (KOI18_family)	C++14	100 / 100	1129 ms	102844 KiB

family

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 300000;
const int MAX_K = 20;

int K;
struct Tree{
	int N, r;
	int p[MAX_N+1];
	bool vst[MAX_N+1];
	vector<int> gp[MAX_N+1];
	int lv[MAX_N+1], par[MAX_N+1][MAX_K+1], in[MAX_N+1], out[MAX_N+1], cnt = 0;
	void dfs(int x){
		if(p[x]==0)	cnt = 0;
		in[x] = ++cnt;	vst[x] = true; lv[x] = (p[x]==0 ? 1 : lv[p[x]]+1);
		par[x][0] = p[x];
		for(int i=1; i<=MAX_K; i++)	par[x][i] = par[par[x][i-1]][i-1];
		for(int i=0; i<gp[x].size(); i++){
			if(gp[x][i]==p[x])	continue;
			p[gp[x][i]] = x;
			dfs(gp[x][i]);
		}
		out[x] = cnt;
	}
	int lca(int x, int y){
		for(int i=MAX_K; i>=0; i--){
			if(lv[par[x][i]]>=lv[y])	x = par[x][i];
			if(lv[par[y][i]]>=lv[x])	y = par[y][i];
		}
		for(int i=MAX_K; i>=0; i--){
			if(par[x][i]!=par[y][i]){
				x = par[x][i]; y = par[y][i];
			}
		}
		if(x!=y)	x = par[x][0];
		return x;
	}
};
Tree T[2];

vector<pii> vt;
vector<pii> upd;
int g[MAX_N+1], l[MAX_N+1], r[MAX_N+1], mlv[MAX_N+1];

void init(int x){
	for(int i=0; i<x; i++){
		g[i] = l[i] = r[i] = i;
		mlv[i] = INF;
	}
}

int find_g(int x){
	return (x==g[x]) ? x : g[x] = find_g(g[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	if(x>y)	{int tmp = x; x = y; y = tmp;}
	g[y] = x;
	r[x] = r[y];
	mlv[x] = min(mlv[x], mlv[y]);
}

bool in[MAX_N+1];

int main(){
	scanf("%d%d%d", &T[0].N, &T[1].N, &K);
	for(int i=0; i<2; i++){
		for(int j=1; j<=T[i].N; j++){
			scanf("%d", &T[i].p[j]);
			if(T[i].p[j]==0)	T[i].r = j;
			else if(i==0)	T[i].gp[T[i].p[j]].pb(j);
		}
		if(i==0)	T[i].dfs(T[i].r);
	}
	for(int i=1; i<=K; i++)		vt.pb({T[0].in[i], i});
	sort(vt.begin(), vt.end());
	for(int i=0; i<K; i++){
		int n = vt[i].second;
		//cout<<n<<" ";
		while(1){
			if(in[n])	break;
			in[n] = true;
			if(T[1].p[n]==0)	break;
			T[1].gp[T[1].p[n]].pb(n);
			n = T[1].p[n];
		}
	}
	T[1].dfs(T[1].r);
	while(!vt.empty())	vt.pop_back();
	for(int i=1; i<=K; i++)		vt.pb({T[1].in[i], i});
	for(int i=1; i<=T[0].N; i++){
		T[0].gp[i].clear();
		in[i] = false;
	}
	sort(vt.begin(), vt.end());
	//cout<<endl;
	for(int i=0; i<K; i++){
		int n = vt[i].second;
		//cout<<n<<" ";
		while(1){
			if(in[n])	break;
			in[n] = true;
			if(T[0].p[n]==0)	break;
			T[0].gp[T[0].p[n]].pb(n);
			n = T[0].p[n];
		}
	}
	T[0].dfs(T[0].r);
	/*cout<<endl;
	for(int i=1; i<=K; i++){
		cout<<T[0].in[i]<<" ";
	}
	cout<<endl;
	for(int i=0; i<K; i++){
		cout<<vt[i].second<<" ";
	}*/
	for(int i=0; i<K-1; i++){
		if(T[0].in[vt[i].second] > T[0].in[vt[i+1].second]){
			printf("NO"); return 0;
		}if(T[1].in[vt[i].second] > T[1].in[vt[i+1].second]){
			printf("NO"); return 0;
		}
	}

	for(int i=0; i<vt.size()-1; i++){
		int n1 = vt[i].second, n2 = vt[i+1].second;
		upd.pb({-T[0].lv[T[0].lca(n1, n2)], i});
	}
	sort(upd.begin(), upd.end());
	init(K);
	int i1, i2, n1, n2, g1, g2, l1, l2, l3, l4, l5, l6;
	for(int i=0; i<upd.size(); i++){
		i1 = upd[i].second; i2 = upd[i].second+1;
		n1 = vt[i1].second; n2 = vt[i2].second;
		g1 = find_g(i1); g2 = find_g(i2);
		l1 = min(T[1].lv[T[1].lca(n1, n2)], min(mlv[g1], mlv[g2]));
		l2 = (g1==0) ? 0 : T[1].lv[T[1].lca(vt[g1-1].second, vt[g1].second)];
		l3 = (r[g2]==K-1) ? 0 : T[1].lv[T[1].lca(vt[r[g2]].second, vt[r[g2]+1].second)];
		l4 = T[0].lv[T[0].lca(n1, n2)];
		l5 = (g1==0) ? INF : T[0].lv[T[0].lca(vt[g1-1].second, vt[g1].second)];
		l6 = (r[g2]==K-1) ? INF : T[0].lv[T[0].lca(vt[r[g2]].second, vt[r[g2]+1].second)];
		//cout<<n1<<" "<<n2<<endl;
		//cout<<l1<<" "<<l2<<" "<<l3<<" "<<l4<<" "<<l5<<" "<<l6<<endl;
		if((l3>l1 && l4!=l6) || (l2>l1 && l4!=l5)){
			printf("NO");
			return 0;
		}
		mlv[find_g(i1)] = min(mlv[find_g(i1)], l1);
		union_g(i1, i2);
	}
	printf("YES");
	return 0;
}

Compilation message (stderr)

family.cpp: In member function 'void Tree::dfs(int)':
family.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<gp[x].size(); i++){
                ~^~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size()-1; i++){
               ~^~~~~~~~~~~~
family.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<upd.size(); i++){
               ~^~~~~~~~~~~
family.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &T[0].N, &T[1].N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &T[i].p[j]);
    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 27 / 27
• Subtask 3: 15 / 15
• Subtask 4: 41 / 41