Submission #63148

#	Time	Username	Problem	Language	Result	Execution time	Memory
63148		khsoo01	족보 (KOI18_family)	C++11	100 / 100	593 ms	80276 KiB

family

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 300005;

int k, par[N], cnt[N];

vector<pair<int,pii> > v;

int Find (int X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

void Union (int X, int Y) {
	X = Find(X);
	Y = Find(Y);
	if(X == Y) return;
	par[Y] = X;
	cnt[X] += cnt[Y];
}

struct tree {
	int n, r, l[N], f[N];
	vector<int> adj[N];
	void input() {
		for(int i=1;i<=n;i++) {
			int T;
			scanf("%d",&T);
			if(!T) r = i;
			else adj[T].push_back(i);
		}
	}
	int calc (int J, int I) {
		if(I <= k) {
			f[I] = I;
			l[I] = 1;
			return I;
		}
		l[I] = 0;
		for(auto &T : adj[I]) {
			f[I] = calc(J, T);
			l[I] += l[T];
		}
		if((int)adj[I].size() != 1) {
			v.push_back({l[I], {J, I}});
		}
		return f[I];
	}
	void solve (int I) {
		for(auto &T : adj[I]) {
			Union(f[T], f[I]);
		}
		if(cnt[Find(f[I])] != l[I]) {
			puts("NO");
			exit(0);
		}
	}
} t[2];

int main()
{
	scanf("%d%d%d",&t[0].n,&t[1].n,&k);
	t[0].input();
	t[1].input();
	t[0].calc(0, t[0].r);
	t[1].calc(1, t[1].r);
	sort(v.begin(), v.end());
	for(int i=1;i<=k;i++) {
		par[i] = i;
		cnt[i] = 1;
	}
	for(auto &T : v) {
		int A, B;
		tie(A, B) = T.Y;
		t[A].solve(B);
	}
	puts("YES");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:66: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: In member function 'void tree::input()':
family.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
    ~~~~~^~~~~~~~~

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