Submission #1064763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064763		Gray	Friend (IOI14_friend)	C++17	19 / 100	1 ms	600 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define ld long double

using namespace std;

vector<vector<int>> A;
vector<int> conf;
vector<pair<int, int>> dp;
void dfs(ll u){
	dp[u].ff+=conf[u];
	for (auto v:A[u]){
		dfs(v);
		dp[u].ff+=dp[v].ss;
		dp[u].ss+=max(dp[v].ss, dp[v].ff);
	}
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	A.clear(); A.resize(n);
	conf.clear(); conf.resize(n);
	dp.clear(); dp.resize(n);
	for (int i=0; i<n; i++) conf[i]=confidence[i];

	for (int i=1; i<n; i++){
		A[host[i]].push_back(i);
	}
	dfs(0);
	return max(dp[0].ff, dp[0].ss);
}

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