oj.uz

답안 #410228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410228 2021-05-22T10:08:06 Z egod1537 족보 (KOI18_family) C++14
0 / 100
 35 ms 60184 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 60148 KB Output is correct
2 Correct 35 ms 60100 KB Output is correct
3 Correct 31 ms 60184 KB Output is correct
4 Incorrect 31 ms 60176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 60148 KB Output is correct
2 Correct 35 ms 60100 KB Output is correct
3 Correct 31 ms 60184 KB Output is correct
4 Incorrect 31 ms 60176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 60148 KB Output is correct
2 Correct 35 ms 60100 KB Output is correct
3 Correct 31 ms 60184 KB Output is correct
4 Incorrect 31 ms 60176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 60148 KB Output is correct
2 Correct 35 ms 60100 KB Output is correct
3 Correct 31 ms 60184 KB Output is correct
4 Incorrect 31 ms 60176 KB Output isn't correct
5 Halted 0 ms 0 KB -