Submission #417817

#	Time	Username	Problem	Language	Result	Execution time	Memory
417817		vanic	Friend (IOI14_friend)	C++14	46 / 100	32 ms	4408 KiB

friend

#include "friend.h"
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iostream>

using namespace std;

const int maxn=1005;

int n;
vector < int > ms[maxn];
int naj;
bool idem[15];
int val[maxn];

void probaj(){
	int sol=0;
	for(int i=0; i<n; i++){
		if(idem[i]){
			sol+=val[i];
			for(int j=0; j<(int)ms[i].size(); j++){
				if(idem[ms[i][j]]){
					return;
				}
			}
		}
	}
	naj=max(naj, sol);
}

void rek(int x){
	if(x==n){
		probaj();
		return;
	}
	idem[x]=1;
	rek(x+1);
	idem[x]=0;
	rek(x+1);
}

int dp[maxn][2];

void dfs(int x, int prosl){
	dp[x][1]=val[x];
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs(ms[x][i], x);
			dp[x][0]+=max(dp[ms[x][i]][0], dp[ms[x][i]][1]);
			dp[x][1]+=dp[ms[x][i]][0];
		}
	}
}

int findSample(int a, int l[], int parent[], int koji[]){
	n=a;
	for(int i=0; i<n; i++){
		val[i]=l[i];
	}
	int ok=0;
	if(n<=1000){
		for(int i=1; i<n; i++){
			if(koji[i]==0){
				ok|=1;
				ms[parent[i]].push_back(i);
				ms[i].push_back(parent[i]);
			}
			else if(koji[i]==1){
				ok|=2;
				for(int j=0; j<(int)ms[parent[i]].size(); j++){
					ms[ms[parent[i]][j]].push_back(i);
					ms[i].push_back(ms[parent[i]][j]);
				}
			}
			else{
				ok|=4;
				for(int j=0; j<(int)ms[parent[i]].size(); j++){
					ms[ms[parent[i]][j]].push_back(i);
					ms[i].push_back(ms[parent[i]][j]);
				}
				ms[parent[i]].push_back(i);
				ms[i].push_back(parent[i]);
			}
		}
	}
	int sol=0;
	if(n<=10){
		rek(0);
		sol=naj;
	}
	else if(n<=1000){
		if(ok==1){
			dfs(0, 0);
			sol=max(dp[0][0], dp[0][1]);
		}
		else if(ok==2){
			for(int i=0; i<n; i++){
				sol+=l[i];
			}
		}
		else if(ok==4){
			for(int i=0; i<n; i++){
				sol=max(sol, l[i]);
			}
		}
		else{
			assert(0);
		}
	}
	else{
		assert(0);
	}
	return sol;
}

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