oj.uz

Submission #158725

# Submission time Handle Problem Language Result Execution time Memory
158725 2019-10-18T13:59:08 Z maruii None (KOI18_family) C++14
0 / 100
 17 ms 14456 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int N, M, K;
struct G {
	vector<int> edge[300005];
	int sz[300005], rep[300005];
	void dfs(int x) {
		if (x && x <= K) rep[x] = x, sz[x] = 1;
		for (auto i : edge[x]) {
			dfs(i);
			rep[x] = rep[i];
			sz[x] += sz[i];
		}
	}
} t1, t2;

int par[300005], sz[300005];
int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); }
void uni(int x, int y) {
	x = fnd(x), y = fnd(y);
	if (x == y) return;
	par[y] = x;
	sz[x] += sz[y];
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M >> K;
	iota(par, par + K + 1, 0);
	fill(sz, sz + K + 1, 1);
	for (int i = 1; i <= N; ++i) {
		int x; cin >> x;
		t1.edge[x].push_back(i);
	}
	for (int i = 1; i <= M; ++i) {
		int x; cin >> x;
		t2.edge[x].push_back(i);
	}
	t1.dfs(0);
	t2.dfs(0);
	vector<pii> vec;
	for (int i = K + 1; i <= N; ++i) vec.emplace_back(t1.sz[i], i);
	for (int i = K + 1; i <= M; ++i) vec.emplace_back(t2.sz[i], -i);
	sort(vec.begin(), vec.end());
	for (auto i : vec) {
		int r;
		if (i.ss < 0) {
			i.ss = -i.ss;
			r = t2.rep[i.ss];
			for (auto j : t2.edge[i.ss]) uni(r, t2.rep[j]);
		}
		else {
			r = t1.rep[i.ss];
			for (auto j : t1.edge[i.ss]) uni(r, t1.rep[j]);
		}
		if (sz[fnd(r)] != i.ff) return !printf("NO");
	}
	printf("YES");
	return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 17 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 17 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 17 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Incorrect 17 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -