oj.uz

Submission #410186

# Submission time Handle Problem Language Result Execution time Memory
410186 2021-05-22T08:18:33 Z egod1537 None (KOI18_family) C++14
0 / 100
 19 ms 35560 KB 
#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

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35440 KB Output is correct
2 Incorrect 19 ms 35560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35440 KB Output is correct
2 Incorrect 19 ms 35560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35440 KB Output is correct
2 Incorrect 19 ms 35560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35440 KB Output is correct
2 Incorrect 19 ms 35560 KB Output isn't correct
3 Halted 0 ms 0 KB -