Submission #58576

#	Time	Username	Problem	Language	Result	Execution time	Memory
58576		aome	Friend (IOI14_friend)	C++17	27 / 100	66 ms	2008 KiB

friend

#include "friend.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
const int INF = 1e9;

int mx;
int res;
int a[N];
int h[N];
int f[N][16];
bool e[N][4];
bool visit[N];
vector<int> G[N];

void add(int u, int v) {
	G[u].push_back(v), G[v].push_back(u);
}

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (!visit[v]) {
			h[v] = h[u] + 1, dfs(v);
		}
		else if (h[u] > h[v]) {
			e[u][h[u] - h[v]] = 1;
		}
	}
}

void solve(int u) {
	visit[u] = 1;
	for (int i = 0; i < 16; ++i) {
		if (i & 1) f[u][i] = a[u];
		for (int j = 1; j < 4; ++j) {
			if ((i & 1) && (i >> j & 1) && e[u][j]) {
				f[u][i] = -INF; break;
			}
		}
	}
	for (auto v : G[u]) {
		if (visit[v]) continue;
		solve(v);
		for (int j = 0; j < 16; ++j) {
			int mask = (j << 1) & 15;
			int tmp = max(f[v][mask], f[v][mask + 1]);
			f[u][j] = max(-INF, f[u][j] + tmp);
		}
	}
	for (int i = 0; i < 16; ++i) mx = max(mx, f[u][i]);
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
	if (n > 1000) return 0;
	for (int i = 0; i < n; ++i) {
		a[i] = confidence[i];
	}
	for (int i = 1; i < n; ++i) {
		if (protocol[i] == 0) {
			add(host[i], i);
		}
		if (protocol[i] == 1) {
			for (auto j : G[host[i]]) add(i, j);
		} 
		if (protocol[i] == 2) {
			for (auto j : G[host[i]]) add(i, j);
			add(host[i], i);
		} 
	}
	for (int i = 0; i < n; ++i) {
		if (!visit[i]) dfs(0);
	}
	memset(visit, 0, sizeof visit);
	for (int i = 0; i < n; ++i) {
		if (visit[i]) continue;
		mx = -INF, solve(i), res += mx;
	}
	return res;
}

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