Submission #1019596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019596		pcc	Friend (IOI14_friend)	C++17	69 / 100	18 ms	4956 KiB

friend

#include "friend.h"

#pragma GCC target("avx2,popcnt,sse4")
#pragma GCC optimize("O3,unroll-loops")
#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;
	int C = 0;
	void dfs(int now){
		C++;
		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[]){
		for(int i = 0;i<n;i++)arr[i] = wei[i];
		for(int i = 1;i<n;i++){
			assert(host[i]<i&&host[i]>=0);
			tree[host[i]].push_back(i);
		}
		dfs(0);
		assert(C == n);
		return ans;
	}
}

namespace BIP{
	const int mxn = 1022;
	bitset<mxn> adj[mxn];
	bitset<mxn> vis,side;
	int n;
	int mat[mxn];
	bool dfs(int now){
		if(vis[now])return false;
		vis[now] = true;
		for(int nxt = 0;nxt<n;nxt++){
			if(!adj[now][nxt])continue;
			if(mat[nxt] == -1||dfs(mat[nxt])){
				mat[nxt] = now;
				mat[now] = nxt;
				return true;
			}
		}
		return false;
	}
	int GO(int nn,int wei[],int host[],int op[]){
		n = nn;
		for(int i = 1;i<n;i++){
			int p = host[i];
			if(op[i] == 0){
				adj[p][i] = adj[i][p] = 1;
				side[i] = (side[p]?0:1);
			}
			else{
				for(int j = 0;j<n;j++){
					adj[i][j] = adj[j][i] = adj[p][j];
				}
				side[i] = side[p];
			}
		}
		int ans = 0;
		memset(mat,-1,sizeof(mat));
		for(int i = 0;i<n;i++){
			vis.reset();
			if(side[i])ans += dfs(i);
		}
		return n-ans;
	}
}


// Find out best sample
int findSample(int n,int wei[],int host[],int op[]){
	set<int> st;
	for(int i = 1;i<n;i++)st.insert(op[i]);
	if(n<=10)return BRUTE::GO(n,wei,host,op);
	else if(st.size() == 2)return BIP::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: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31