Submission #285589

#	Time	Username	Problem	Language	Result	Execution time	Memory
285589		emanIaicepsa	Friend (IOI14_friend)	C++14	11 / 100	1085 ms	4728 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define vi vector<int>
using namespace std;
// Find out best sample
/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/
bool f[1005][1005];
void addedge(int x,int h, int ope){
	if(ope == 0) f[x][h] = f[h][x] = 1;
	else if(ope == 1){
		for(int i=0;i<x;i++){
			if(f[h][i]) f[x][i] = f[i][x] = 1;
		}
	}
	else{
		for(int i=0;i<x;i++){
			if(i == h || f[h][i]) f[i][x] = f[x][i] = 1;
		}
	}
}

bool ok(vi &v){
	/* for(auto i:v) cout<<i<<" "; cout<<'\n'; */
	int n = v.size();
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(f[v[i]][v[j]]) return 0;
	return 1;
}

int findSample(int n,int conf[],int host[],int ope[]){
	for(int i=1;i<n;i++){
		addedge(i, host[i], ope[i]);
	}
	/* for(int i=0;i<n;i++){ */
	/* 	for(int j=0;j<n;j++){ */
	/* 		cout<<f[i][j]<<" \n"[j==n-1]; */
	/* 	} */
	/* } */
	int all = 1<<n, ans = 0;
	for(int i=1;i<all;i++){
		vector<int> v;
		for(int j=0;j<n;j++){
			if(i>>j&1) v.pb(j);
		}
		if(ok(v)){
			int ta = 0;
			for(auto &x:v) ta += conf[x];
			ans = max(ans, ta);
		}
	}
	return ans;
}

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