Submission #297949

#	Time	Username	Problem	Language	Result	Execution time	Memory
297949		Plurm	Friend (IOI14_friend)	C++11	35 / 100	60 ms	8568 KiB

friend

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

vector<int> g[100005];
vector<int> sg[100005];
int rn[100005];
int dp[100005][2]; // dp[u][including u?]
void dfs(int u, int* confidence, int p = -1){
	for(int v : g[u]){
		dfs(v, confidence, u);
	}
	for(int v : sg[u]){
		dfs(v, confidence, u);
	}
	// compute dp[u][0]
	for(int v : g[u]){
		dp[u][0] += max(dp[v][0], dp[v][1]);
	}
	for(int v : sg[u]){
		dp[u][0] += dp[v][0];
	}
	int qs = 0;
	int cdd = 0;
	for(int v : sg[u]){
		qs += max(dp[v][0], dp[v][1]);
		for(int vv : g[u]){
			if(vv > v){
				cdd += max(dp[vv][0], dp[vv][1]);
			}else{
				cdd += dp[vv][0];
			}
		}
		dp[u][1] = max(dp[u][1], qs + cdd);
		cdd = 0;
	}
	// compute dp[u][1]
	qs += confidence[u];
	for(int v : g[u]){
		cdd += dp[v][0];
	}
	dp[u][1] = max(dp[u][1], qs + cdd);
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	for(int i = 0; i < n; i++) rn[i] = i;
	for(int i = 1; i < n; i++){
		switch(protocol[i]){
		case 0:
			g[rn[host[i]]].push_back(i);
			break;
		case 1:
			sg[rn[host[i]]].push_back(i);
			break;
		case 2:
			rn[i] = rn[host[i]];
			confidence[rn[host[i]]] = max(confidence[rn[host[i]]], confidence[i]);
			break;
		}
	}
	dfs(0, confidence);
	return max(dp[0][0], dp[0][1]);
}

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