Submission #254540

#	Time	Username	Problem	Language	Result	Execution time	Memory
254540		b00n0rp	친구 (IOI14_friend)	C++17	35 / 100	1 ms	512 KiB

friend

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

int dp[1005][2],val[1005];
vector<int> adj[1005];

void dfs(int u){
	for(auto v:adj[u]){
		dfs(v);
		dp[u][1] += dp[v][0];
		dp[u][0] += dp[v][1];
	}
	dp[u][1] += val[u];
	dp[u][1] = max(dp[u][1],dp[u][0]);
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	int type0 = 0,type1 = 0,type2 = 0;
	int ans = 0;
	for(int i = 1; i < n; i ++){
		type0 |= (protocol[i]==0);
		type1 |= (protocol[i]==1);
		type2 |= (protocol[i]==2);
	}
	if(type0 and (!type1) and (!type2)){
		for(int i = 1; i < n; i ++){
			val[i] = confidence[i];
			adj[host[i]].push_back(i);
		}
		val[0] = confidence[0];
		dfs(0);
		ans = dp[0][1];
	}
	else if(type1 and (!type0) and (!type2)){
		for(int i = 0; i < n; i ++) ans += confidence[i];
	}
	else if(type2 and (!type1) and (!type0)){
		for(int i = 0; i < n; i ++) ans = max(ans,confidence[i]);
	}
	else{

	}
	return ans;
}

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