Submission #410186

#	Time	Username	Problem	Language	Result	Execution time	Memory
410186		egod1537	족보 (KOI18_family)	C++14	0 / 100	19 ms	35560 KiB

family

#include <bits/stdc++.h>

using namespace std;

int dsu[300001], pa[300001], pb[300001];

vector<int> S[300001];
vector<int> A[300001], B[300001];
vector<int> depA[300001], depB[300001];

int find(int x) {
	return (dsu[x] == 0) ? x : (dsu[x] = find(dsu[x]));
}
void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	dsu[b] = a;
}

int da, db;
void dfsA(int pos, int dep) {
	depA[dep].push_back(pos);
	da = max(da, dep);
	for (int w : A[pos]) dfsA(w, dep+1);
}
void dfsB(int pos, int dep) {
	depB[dep].push_back(pos);
	db = max(db, dep);
	for (int w : B[pos]) dfsB(w, dep + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int n, m, k; cin >> n >> m >> k;
	int aroot = 0, broot=0;
	for (int i = 1; i <= n; i++) {
		cin >> pa[i]; if (pa[i] == 0) aroot = i;
		A[pa[i]].push_back(i);
		if (i <= k) S[pa[i]].push_back(i);
	}
	for (int i = 1; i <= m; i++) {
		cin >> pb[i]; if (pb[i] == 0) broot = i;
		B[pb[i]].push_back(i);
	}

	dfsA(aroot, 1), dfsB(broot, 1);

	db--;
	for (int d : depB[db])
		for (int w : B[d])
			merge(d, w);

	bool ans = true;
	while (da--) {
		if (da < db) {
			db--;
			for (int d : depB[db])
				for (int w : B[d])
					merge(d, w);
		}

		//자신의 현재 집합에서 다른 집합의 애들이 있는지
		for (int d : depA[da]) {
			int prev = -1;
			for (int w : S[d]) {
				if (prev == -1) prev = find(w);
				if (prev != find(w)) {
					cout << "NO";
					return 0;
				}
			}
		}

		//자신의 부모로 집합 옮기기
		for (int d : depA[da]) {
			for (int w : A[d])
				S[pa[d]].push_back(w);
		}
	}

	cout << "YES";

	return 0;
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:55:7: warning: unused variable 'ans' [-Wunused-variable]
   55 |  bool ans = true;
      |       ^~~

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