Submission #739213

#	Time	Username	Problem	Language	Result	Execution time	Memory
739213		NeroZein	Friend (IOI14_friend)	C++17	19 / 100	79 ms	1276 KiB

friend

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

const int N = 1003;

int n; 
int a[N]; 
int vis[N]; 
int dp[N][2]; 
vector<int> g[N]; 

int findSample(int n_, int confidence[],int host[],int protocol[]){
	n = n_; 
	for (int i = 0; i < n; ++i) {
		a[i] = confidence[i]; 
	}
	for (int i = 1; i < n; ++i) {
		assert(host[i] < i); 
		if (protocol[i] == 0) {
			g[host[i]].push_back(i);
			g[i].push_back(host[i]);
		}
		else {
			for (int j : g[host[i]]) {
				g[j].push_back(i);
				g[i].push_back(j);
			}
			if (protocol[i] == 2) {
				g[i].push_back(host[i]); 
				g[host[i]].push_back(i);				
			}
		}
	}
	int ans = 0; 
	function<void(int, int)> Dfs = [&](int v, int p) {
		int sum0 = 0, sum1 = 0; 
		vis[v] = true; 
		for (int u : g[v]) {
			if (vis[u]) {
				continue; 
			}
			Dfs(u, v);
			sum0 += dp[u][0];
			sum1 += dp[u][1]; 
		}
		dp[v][0] = sum1; 
		dp[v][1] = max(a[v] + sum0, sum1);
	};
	for (int i = 0; i < n; ++i) {
		memset(dp, 0, sizeof dp); 
		memset(vis, 0, sizeof vis); 
		Dfs(i, i); 
		ans = max(ans, dp[i][1]); 
	} 
	return ans;
}

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