Submission #410228

#	Time	Username	Problem	Language	Result	Execution time	Memory
410228		egod1537	족보 (KOI18_family)	C++14	0 / 100	35 ms	60184 KiB

family

#include <bits/stdc++.h>

using namespace std;

#define MAX 300001

vector<int> A[MAX], B[MAX];
vector<int> newA[MAX], newB[MAX];
int pa[MAX], pb[MAX];

int dsu[MAX];
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 num = 0;
void dfsA(int pos) {
	num++;
	for (int w : A[pos]) {
		newA[find(pos)].push_back(find(w));
		dfsA(w);
	}
}
void dfsB(int pos) {
	num++;
	for (int w : B[pos]) {
		newB[find(pos)].push_back(find(w));
		dfsB(w);
	}
}

vector<int> depA[MAX], depB[MAX];

int da, db;
void dfsdepA(int pos, int dep) {
	depA[dep].push_back(pos);
	da = max(da, dep);
	for (int w : newA[pos]) {
		if (w == pos) continue;
		pa[w] = pos, dfsdepA(w, dep + 1);
	}
}
void dfsdepB(int pos, int dep) {
	depB[dep].push_back(pos);
	db = max(db, dep);
	for (int w : newB[pos]) {
		if (w == pos) continue;
		pb[w] = pos, dfsdepB(w, dep + 1);
	}
}

vector<int> Sa[MAX], Sb[MAX];

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);
	}
	for (int i = 1; i <= m; i++) {
		cin >> pb[i]; if (pb[i] == 0) broot = i;
		B[pb[i]].push_back(i);
	}

	int asz = 0, bsz = 0;
	memset(dsu, 0, sizeof(dsu));
	for (int i = 1; i <= n; i++)
		if (A[i].size() == 1) merge(pa[i], i);
	num = 0, dfsA(aroot);
	asz = num;
	for (int i = 1; i <= asz; i++) {
		vector<int>& now = newA[i];
		sort(now.begin(), now.end());
		now.erase(unique(now.begin(), now.end()), now.end());
	}

	memset(dsu, 0, sizeof(dsu));
	for (int i = 1; i <= m; i++)
		if (B[i].size() == 1) merge(pb[i], i);
	num = 0, dfsB(broot);
	bsz = num;
	for (int i = 1; i <= bsz; i++) {
		vector<int>& now = newB[i];
		sort(now.begin(), now.end());
		now.erase(unique(now.begin(), now.end()), now.end());
	}

	//for (int i = 1; i <= asz; i++) {
	//	cout << i << " : ";
	//	for (int w : newA[i]) cout << w << " ";
	//	cout << "\n";
	//}
	//cout << "\n";
	//for (int i = 1; i <= bsz; i++) {
	//	cout << i << " : ";
	//	for (int w : newB[i]) cout << w << " ";
	//	cout << "\n";
	//}

	memset(pa, 0, sizeof(pa)); memset(pb, 0, sizeof(pb));
	dfsdepA(aroot, 1), dfsdepB(broot, 1);

	//cout << "sz : " << da << " " << db << "\n";

	if (da < db) {
		swap(da, db);
		for (int i = 0; i <= 300000; i++)
			swap(depA[i], depB[i]);
	}

	memset(dsu, 0, sizeof(dsu));
	for (int i = 1; i <= k; i++) {
		Sa[pa[i]].push_back(i);
		merge(pa[i], i);
		Sb[pb[i]].push_back(i);
	}

	da--, db--;
	while (da > db) {
		for (int d : depA[da])
			for (int w : Sa[d]) {
				Sa[pa[d]].push_back(w);
				merge(pa[d], w);
			}
		da--;
	}

	while (da > 0 || db > 0) {
		for (int d : depB[db]) {
			int prev = -1;
			for (int w : Sb[d]) {
				if (prev == -1) prev = find(w);
				if (prev != find(w)) {
					cout << "NO";
					return 0;
				}
			}
		}

		for (int d : depB[db])
			for (int w : Sb[d]) {
				Sb[pb[d]].push_back(w);
			}
		for (int d : depA[da])
			for (int w : Sa[d]) {
				Sa[pa[d]].push_back(w);
				merge(pa[d], w);
			}
		da--, db--;
	}

	cout << "YES";

	return 0;
}

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