Submission #1074626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074626		Malix	Friend (IOI14_friend)	C++14	8 / 100	147 ms	65536 KiB

friend

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

#define REP(a,b,c) for(int a=b;a<c;a++)
#define F first
#define S second
#define PB push_back

typedef long long ll;
typedef vector<u_int16_t> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;

vii a;
u_int16_t dp[1010][2];
int n;
vi prt,hst,c,p;
vi val;
set<u_int16_t> s1,s2;

int brute(int confidence[]){
	u_int16_t m=pow(2,n);
	u_int16_t ans=0;
	REP(i,0,n)sort(a[i].begin(),a[i].end());
	REP(i,1,m){
		u_int16_t k=0;
		set<int> st;
		REP(j,0,n){
			if(i&(1<<j))st.insert(j);
		}
		bool flag=1;
		for(auto u:st){
			for(auto v:a[u]){
				if(st.count(v)!=0)flag=0;
			}
		}
		for(auto u:st)k+=confidence[u];
		if(flag)ans=max(ans,k);
	}
	return ans;
}

void solve(int x){
	u_int16_t mx=0,mx2=0;
	for(auto u:a[x])if(p[x]!=u){
		p[u]=x;
		solve(u);
		mx+=max(dp[u][0],dp[u][1]);
		mx2+=dp[u][0];
	}
	dp[x][1]+=mx2;
	dp[x][0]+=mx;
}

void calc(int x){
	int mx1=0,mx2=0;
	s1.clear();s2.clear();
	for(auto u:a[x])if(p[x]!=u){
		p[u]=x;
		calc(u);
		for(auto v:a[u])if(v!=x)s1.insert(v);
	}
	for(auto u:s1)for(auto v:a[u])if(p[u]!=v)s2.insert(v);
	for(auto u:s1)mx1+=val[u];
	for(auto u:s2)mx2+=val[u];
	val[x]+=max(mx1,mx2);
}

// Find out best sample
int findSample(int N,int confidence[],int host[],int protocol[]){
	n=N;
	prt.resize(n);hst.resize(n);c.resize(n);
	REP(i,1,n)hst[i]=host[i];
	REP(i,1,n)prt[i]=protocol[i];
	REP(i,0,n)c[i]=confidence[i];
	bool flag=1,flag2=1,flag3=1;
	REP(i,1,n)if(prt[i]!=2)flag=0;
	REP(i,1,n)if(prt[i]!=1)flag2=0;
	REP(i,1,n)if(prt[i]!=0)flag3=0;
	if(flag)return *max_element(confidence,confidence+n);
	int sm=0;
	REP(i,0,n)sm+=c[i];
	if(flag2)return sm;
	a.resize(n);
	REP(i,1,n){
		int pos=host[i];
		if(protocol[i]==0||protocol[i]==2){
			a[pos].PB(i);
			a[i].PB(pos);
		}
		if(protocol[i]==1||protocol[i]==2){
			for(auto u:a[pos])if(u!=i){
				a[u].PB(i);
				a[i].PB(u);
			}
		}
	}
	if(n<=10)return brute(confidence);
	if(flag3){
		p.resize(n,-1);
		REP(i,0,n)dp[i][1]=c[i];
		REP(i,0,n)dp[i][0]=0;
		solve(0);
		return max(dp[0][0],dp[0][1]);
	}
	p.resize(n,-1);val.resize(n,0);
	REP(i,0,n)val[i]+=c[i];
	calc(0);//do dfs and find
	return *max_element(val.begin(),val.end());
}

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