제출 #254546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254546		b00n0rp	친구 (IOI14_friend)	C++17	46 / 100	40 ms	6136 KiB

friend

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

int dp[1005][2],val[1005];
vector<int> adj[1005];
bool gg[1005][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{
		for(int i = 1; i < n; i ++){
			if(protocol[i] == 0){
				gg[i][host[i]] = 1;
				gg[host[i]][i] = 1;
			}
			else if(protocol[i] == 1){
				for(int j = 0; j < n; j ++){
					gg[i][j] = gg[host[i]][j];
					gg[j][i] = gg[i][j];
				}
			}
			else{
				for(int j = 0; j < n; j ++){
					gg[i][j] = gg[host[i]][j];
					gg[j][i] = gg[i][j];
				}
				gg[i][host[i]] = 1;
				gg[host[i]][i] = 1;
			}
		}
		for(int i = 0; i < (1<<n); i ++){
			vector<int> v;
			int cur = 0;
			for(int j = 0; j < n; j ++){
				if((1<<j)&i){
					v.push_back(j);
					cur += confidence[j];
				}
			}
			for(auto j1:v) for(auto j2:v) if(gg[j1][j2]) cur = 0;
			ans = max(ans,cur);
		}
	}
	return ans;
}

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