Submission #65655

#	Time	Username	Problem	Language	Result	Execution time	Memory
65655		sebinkim	족보 (KOI18_family)	C++14	100 / 100	789 ms	129812 KiB

family

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> V1[303030], V2[303030];
int L1[303030], L2[303030], R1[303030], R2[303030];
int P1[303030][20], P2[303030];
int I[303030];
multiset <int> S[303030];
int n, m, k, cnt1, cnt2, r1, r2;

void check(int x, int l, int r)
{
	int i, p = I[l], s = 0, f1, f2;
	
	for(i=19; i>=0; i--){
		if(!(L1[P1[p][i]] <= l && r <= R1[P1[p][i]])) p = P1[p][i];
	}
	p = P1[p][0];
	
	for(int t: V1[p]){
		auto it = S[x].lower_bound(L1[t]);
		if(it != S[x].end() && L1[t] <= *it && *it <= R1[t]) s += R1[t] - L1[t] + 1;
	}
	
	if(s != R2[x] - L2[x] + 1){
		printf("NO\n");
		exit(0);
	}
}

void dfs1(int p)
{
	if(p <= k){
		cnt1 ++;
		L1[p] = R1[p] = cnt1;
		I[cnt1] = p;
		return;
	}
	L1[p] = cnt1 + 1;
	for(int t: V1[p]) dfs1(t);
	R1[p] = cnt1;
}

pii dfs2(int p)
{
	if(p <= k){
		cnt2 ++;
		L2[p] = R2[p] = cnt2;
		S[p].insert(L1[p]);
		return pii(L1[p], L1[p]);
	}
	
	pii ret = pii(1e9, -1e9), k;
	
	L2[p] = cnt2 + 1;
	
	for(int t: V2[p]){
		k = dfs2(t);
		if(S[p].size() < S[t].size()) swap(S[t], S[p]);
		for(auto &v: S[t]) S[p].insert(v);
		
		ret.first = min(ret.first, k.first);
		ret.second = max(ret.second, k.second);
	}
	
	R2[p] = cnt2;
	
	check(p, ret.first, ret.second);
	
	return ret;
}

int main()
{
	int i, j;
	
	scanf("%d%d%d", &n, &m, &k);
	
	for(i=1; i<=n; i++){
		scanf("%d", P1[i]);
		if(P1[i][0] == 0) r1 = i;
		else V1[P1[i][0]].push_back(i);
	}
	
	for(i=1; i<=19; i++){
		for(j=1; j<=n; j++){
			P1[j][i] = P1[P1[j][i-1]][i-1];
		}
	}
	
	for(i=1; i<=m; i++){
		scanf("%d", P2+i);
		if(P2[i] == 0) r2 = i;
		V2[P2[i]].push_back(i);
	}
	
	L1[0] = 1, R1[0] = k;
	dfs1(r1);
	
	L2[0] = 1, R2[0] = k;
	dfs2(r2);
	
	printf("YES\n");
	
	return 0;
}

Compilation message (stderr)

family.cpp: In function 'void check(int, int, int)':
family.cpp:16:26: warning: unused variable 'f1' [-Wunused-variable]
  int i, p = I[l], s = 0, f1, f2;
                          ^~
family.cpp:16:30: warning: unused variable 'f2' [-Wunused-variable]
  int i, p = I[l], s = 0, f1, f2;
                              ^~
family.cpp: In function 'int main()':
family.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
family.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", P1[i]);
   ~~~~~^~~~~~~~~~~~~
family.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", P2+i);
   ~~~~~^~~~~~~~~~~~

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