Submission #410164

#	Time	Username	Problem	Language	Result	Execution time	Memory
410164		egod1537	족보 (KOI18_family)	C++14	0 / 100	3 ms	2636 KiB

family

#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 (stderr)

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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41