Submission #313635

#	Time	Username	Problem	Language	Result	Execution time	Memory
313635		tengiz05	Friend (IOI14_friend)	C++17	69 / 100	44 ms	10368 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5+5;
int dp[N][2];
int a[N];
int used[N], match[N];
vector<int> edges[N];
vector<int> r, b;
void dfs(int u, int p){
	dp[u][1] = a[u];
	for(auto v : edges[u]){
		if(v == p)continue;
		dfs(v, u);
		dp[u][0] += dp[v][1];
		dp[u][1] += dp[v][0];
	}
	dp[u][1] = max(dp[u][1], dp[u][0]);
}
void bipart(int u, int col=0){
	if(col == 0)r.pb(u);
	else b.pb(u);
	used[u] = true;
	for(auto v : edges[u]){
		if(used[v])continue;
		bipart(v, col^1);
	}
}
bool check(int u, int t){
	used[u]=t;
	for(auto v : edges[u]){
		if(match[v]==-1 || used[match[v]]!=t && check(match[v], t)) {
			match[v]=u;
			return 1;
		}
	}return 0;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=0;
	for(int i=0;i<n;i++)a[i] = confidence[i];
	bool all0=true, all1=true, all2=true;
	for(int i=1;i<n;i++){
		if(protocol[i] != 0)all0=false;
		if(protocol[i] != 1)all1=false;
		if(protocol[i] != 2)all2=false;
	}
	if(n <= 15){
		int mask = 0;
		vector<int> friends[16];
		for(int i=1;i<n;i++){
			if(protocol[i] == 0){
				friends[i].pb(host[i]);
				friends[host[i]].pb(i);
			}else {
				for(auto x : friends[host[i]]){
					friends[i].pb(x);
					friends[x].pb(i);
				}
				if(protocol[i] == 2){
					friends[i].pb(host[i]);
					friends[host[i]].pb(i);
				}
			}
		}
		mask = 1;
		while(mask < (1<<n)){
			int cost = 0;
			vector<bool> used(n);
			for(int i=0;i<n;i++){
				if(!((1<<i)&mask))continue;
				bool ok = true;
				for(auto x : friends[i])if(used[x])ok=false;
				if(ok)cost += confidence[i], used[i] = true;
			}
			ans = max(cost, ans);
			mask++;
		}
	}else if(all1){
		for(int i=0;i<n;i++)ans += confidence[i];
	}else if(all2){
		for(int i=0;i<n;i++)ans = max(ans, confidence[i]);
	}else if(all0){
		for(int i=1;i<n;i++){
			edges[i].pb(host[i]);
			edges[host[i]].pb(i);
		}
		dfs(0, 0);
		ans = max(dp[0][0], dp[0][1]);
	}else {
		vector<int> friends[1005];
		for(int i=1;i<n;i++){
			if(protocol[i] == 0){
				friends[i].pb(host[i]);
				friends[host[i]].pb(i);
				edges[i].pb(host[i]);
				edges[host[i]].pb(i);
			}else {
				for(auto x : friends[host[i]]){
					friends[i].pb(x);
					friends[x].pb(i);
					edges[i].pb(x);
					edges[x].pb(i);
				}
				if(protocol[i] == 2){
					friends[i].pb(host[i]);
					friends[host[i]].pb(i);
					edges[i].pb(host[i]);
					edges[host[i]].pb(i);
				}
			}
		}
		for(int i=0;i<n;i++)if(!used[i])bipart(i);
		int st = 1001, tt = 1002;
		for(auto x : r)edges[st].pb(x);
		for(auto x : b)edges[x].pb(tt);
		for(int i=0;i<n;i++)match[i] = -1;
		int timer = 0;
		for(auto u : r){
			timer++;
			ans += check(u, timer);
		}ans = n-ans;
	}
	return ans;
}

Compilation message (stderr)

friend.cpp: In function 'bool check(int, int)':
friend.cpp:33:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |   if(match[v]==-1 || used[match[v]]!=t && check(match[v], t)) {
      |                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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