Submission #1019509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019509		pcc	Friend (IOI14_friend)	C++17	27 / 100	17 ms	4952 KiB

friend

#include "friend.h"

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

namespace BRUTE{
	const int mxn = 11;
	vector<int> paths[mxn];
	int GO(int n,int wei[],int host[],int op[]){
		for(int i = 1;i<n;i++){
			int p = host[i];
			if(op[i] == 0){
				paths[i].push_back(p);
			}
			else if(op[i] == 1){
				paths[i] = paths[p];
			}
			else{
				paths[i] = paths[p];
				paths[i].push_back(p);
			}
			for(auto &j:paths[i])paths[j].push_back(i);
		}
		int ans = 0;
		for(int i = 0;i<(1<<n);i++){
			bool flag = true;
			int sum = 0;
			for(int j = 0;j<n;j++){
				if(!(i&(1<<j)))continue;
				sum += wei[j];
				for(auto nxt:paths[j]){
					if(i&(1<<nxt))flag = false;
				}
			}
			if(!flag)continue;
			ans = max(ans,sum);
		}
		return ans;
	}
}

namespace TREE{
	const int mxn = 1e5+10;
	vector<int> tree[mxn];
	int arr[mxn];
	int dp[mxn][2];
	int ans;
	void dfs(int now){
		dp[now][0] = dp[now][1] = 0;
		for(auto nxt:tree[now]){
			dfs(nxt);
			dp[now][0] += max(dp[nxt][0],dp[nxt][1]);
			dp[now][1] += dp[nxt][0];
		}
		dp[now][1] += arr[now];
		ans = max({ans,dp[now][0],dp[now][1]});
		return;
	}
	int GO(int n,int wei[],int host[],int op[]){
		int ans = 0;
		for(int i = 0;i<n;i++)arr[i] = wei[i];
		for(int i = 1;i<n;i++){
			tree[host[i]].push_back(i);
		}
		dfs(0);
		return ans;
	}
}

// Find out best sample
int findSample(int n,int wei[],int host[],int op[]){
	if(n<=10)return BRUTE::GO(n,wei,host,op);
	else if(op[1] == 0)return TREE::GO(n,wei,host,op);
	else if(op[2] == 1){
		int re = 0;
		for(int i = 0;i<n;i++)re += wei[i];
		return re;
	}
	else return *max_element(wei,wei+n);
}

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