Submission #1181678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181678		stdfloat	Friend (IOI14_friend)	C++20	35 / 100	21 ms	4496 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
using namespace std;

vector<bool> vis;

vector<vector<int>> E, dp;

void dfs(int x) {
	vis[x] = true;
	for (auto i : E[x]) {
		if (vis[i]) continue;

		dfs(i);
	
		dp[x][0] += max(dp[i][1], dp[i][0]); dp[x][1] += dp[i][0];
	}
}

int findSample(int n, int cnfd[], int hst[], int prt[]) {
	E.assign(n, {});
	vector<int> cnt(3);
	for (int i = 1; i < n; i++) {
		cnt[prt[i]]++;

		if (prt[i]) {
			for (auto j : E[hst[i]]) {
				E[j].push_back(i);
				E[i].push_back(j);
			}
		}
		if (prt[i] != 1) {
			E[hst[i]].push_back(i);
			E[i].push_back(hst[i]);
		}
	}

	if (!cnt[2]) {
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			vis.assign(n, false);
			dp.assign(n, vector<int>(2));
			for (int i = 0; i < n; i++)
				dp[i][1] = cnfd[i];

			dfs(i);

			v[i] = max(dp[i][0], dp[i][1]);
		}

		int sm = 0;
		vis.assign(n, false);
		for (int i = 0; i < n; i++) {
			if (vis[i]) continue;

			int mx = v[i];
			queue<int> q;
			q.push(i); vis[i] = true;
			while (!q.empty()) {
				int x = q.front(); q.pop();

				for (auto j : E[x]) {
					if (!vis[j]) {
						vis[j] = true;
						mx = max(mx, v[j]);
						q.push(j);
					}
				}
			}

			sm += mx;
		}

		return sm;
	}
	else if (cnt[0] == n - 1) {
		vis.assign(n, false);
		dp.assign(n, vector<int>(2));
		for (int i = 0; i < n; i++)
			dp[i][1] = cnfd[i];

		dfs(0);

		return max(dp[0][0], dp[0][1]);
	}
	else if (cnt[1] == n - 1) {
		int sm = 0;
		for (int i = 0; i < n; i++)
			sm += cnfd[i];

		return sm;
	}
	else if (cnt[2] == n - 1) {
		int sm = 0;
		vector<bool> vis(n);
		for (int i = 0; i < n; i++) {
			if (vis[i]) continue;

			int mx = cnfd[i];
			for (auto j : E[i]) {
				vis[j] = true;
				mx = max(mx, cnfd[j]);
			}

			sm += mx;
		}

		return sm;
	}

	assert(false);
}

• Subtask 1: 0 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31