oj.uz

Submission #410164

# Submission time Handle Problem Language Result Execution time Memory
410164 2021-05-22T06:49:55 Z egod1537 None (KOI18_family) C++14
0 / 100
 3 ms 2636 KB 
#include <bits/stdc++.h>

using namespace std;

int dsu[300001], cnt[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;
	cnt[a] += cnt[b];
}

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

	int n, m, k; cin >> n >> m >> k;
	vector<int> Ap, Bp;

	memset(dsu, 0, sizeof(dsu));
	fill(cnt, cnt+300001, 1);
	for (int i = 1; i <= n; i++) {
		int p; cin >> p;
		if (p == 0) continue;
		if (i <= k)
			Ap.push_back(p), merge(p, i);
	}
	sort(Ap.begin(), Ap.end());
	Ap.erase(unique(Ap.begin(), Ap.end()), Ap.end());

	vector<int> acnt, bcnt;
	for (int w : Ap) acnt.push_back(cnt[find(w)]-1);
	
	memset(dsu, 0, sizeof(dsu));
	fill(cnt, cnt + 300001, 1);
	for (int i = 1; i <= m; i++) {
		int p; cin >> p;
		if (p == 0) continue;
		if (i <= k)
			Bp.push_back(p), merge(p, i);
	}

	sort(Bp.begin(), Bp.end());
	Bp.erase(unique(Bp.begin(), Bp.end()), Bp.end());
	for (int w : Bp) bcnt.push_back(cnt[find(w)]-1);

	bool no = false;
	int p = 0;
	for (int w : acnt) {
		if (p == bcnt.size()) {
			cout << "NO";
			return 0;
		}
		bcnt[p] -= w;
		if (bcnt[p] == 0) p++;
		else if (bcnt[p] < 0) {
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";

	return 0;
}

Compilation message

family.cpp: In function 'int main()':
family.cpp:54:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if (p == bcnt.size()) {
      |       ~~^~~~~~~~~~~~~~
family.cpp:51:7: warning: unused variable 'no' [-Wunused-variable]
   51 |  bool no = false;
      |       ^~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 41.0

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