Submission #780317

#	Time	Username	Problem	Language	Result	Execution time	Memory
780317		fatemetmhr	Friend (IOI14_friend)	C++17	69 / 100	527 ms	62572 KiB

friend

//  ~ Be Name Khoda ~  //

#include "friend.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int cmp[maxn5], hs[maxn5], ty[maxn5];
ll val[maxn5];
int n, dp[maxn5][2], mat[maxn5];
vector <int> adj[maxn5];
bool mark[maxn5];

int sub1(){
	for(int i = 1; i < n; i++){
		if(ty[i] == 0){
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
		else if(ty[i] == 1){
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
		}
		else{
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
			adj[hs[i]].pb(i);
			adj[i].pb(hs[i]);
		}
	}

	int ans = 0;
	for(int mask = 1; mask < (1 << n); mask++){
		bool re = true;
		for(int i = 0; i < n; i++) if((mask >> i)&1)
			for(auto u : adj[i]) if((mask >> u)&1)
				re = false;
		if(re){
			int sum = 0;
			for(int i = 0; i < n; i++) if((mask >> i)&1)
				sum += val[i];
			ans = max(ans, sum);
		}
	}
	return ans;
}	

int sub2(){
	ll sum = 0;
	for(int i = 0; i < n; i++)
		sum += val[i];
	return sum;
}

int sub3(){
	ll mx = 0;
	for(int i = 0; i < n; i++)
		mx = max(mx, val[i]);
	return mx;
}

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

int sub4(){
	for(int i = 1; i < n; i++)
		adj[hs[i]].pb(i);
	dfs4(0);
	return max(dp[0][0], dp[0][1]);
}

bool dfs5(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(mat[u] == -1 || (!mark[mat[u]] && dfs5(mat[u]))){
		mat[v] = u;
		mat[u] = v;
		return true;
	}
	return false;
}

int sub5(){
	for(int i = 1; i < n; i++){
		cmp[i] = cmp[hs[i]] ^ ty[i] ^ 1;
		if(ty[i] == 0){
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
		else{
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
		}
	}
	bool con = true;
	memset(mat, -1, sizeof mat);
	int ans = 0;
	while(con){
		con = false;
		memset(mark, false, sizeof mark);
		for(int i = 0; i < n; i++) if(!mark[i] && cmp[i] && mat[i] == -1 && dfs5(i)){
			con = true;
			ans++;
		}
	}
	return n - ans;
}	

// Find out best sample
int findSample(int n,int confidence[], int host[], int protocol[]){
	::n = n;
	for(int i = 1; i < n; i++){
		val[i] = confidence[i];
		hs[i] = host[i];
		ty[i] = protocol[i];
	}
	val[0] = confidence[0];
	if(n <= 10)
		return sub1();
	bool ok = true;
	for(int i = 1; i < n; i++)
		ok &= (protocol[i] == protocol[1]);
	if(ok){
		if(protocol[1] == 0)
			return sub4();
		if(protocol[1] == 1)
			return sub2();
		return sub3();
	}
	return sub5();
}

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