Submission #298110

#	Time	Username	Problem	Language	Result	Execution time	Memory
298110		mieszko11b	Friend (IOI14_friend)	C++14	23 / 100	5 ms	512 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

bool subtask[6];
int G[20][20];

void add_edge(int a, int b) {
	G[a][b] = 1;
	G[b][a] = 1;
	//~ cout << a << " " << b << endl;
}

vector<int> c;
int dp[1007][2];
vector<int> ch[1007];

vector<int> GG[1007];
int match[1007];
int clr[1007];
int viscnt;
int vis[1007];

void dfs(int w) {
	dp[w][1] = c[w];
	for(int u : ch[w]) {
		dfs(u);
		dp[w][0] += max(dp[u][0], dp[u][1]);
		dp[w][1] += dp[u][0];
	}
}

void add_edge2(int a, int b) {
	GG[a].push_back(b);
	GG[b].push_back(a);
	//~ cout << a << " " << b << endl;
}

int dfs2(int w) {
	if(vis[w] == viscnt)
		return 0;
	vis[w] = viscnt;
	
	for(int u : GG[w]) {
		if(match[u] == -1 || dfs2(match[u])) {
			match[w] = u;
			match[u] = w;
			return 1;
		}
	}
	
	return 0;
}

int findSample(int n,int confidence[],int host[],int protocol[]) {
	for(int i = 1 ; i<= 5 ; i++)
		subtask[i] = 1;
	if(n > 10)
		subtask[1] = 0;
		
	for(int i = 1 ; i < n ; i++) {
		if(protocol[i] == 0)
			subtask[2] = subtask[3] = 0;
		if(protocol[i] == 1)
			subtask[3] = subtask[4] = 0;
		if(protocol[i] == 2)
			subtask[2] = subtask[4] = subtask[5] = 0;
	}
	
	//~ if(subtask[1]) {
		//~ for(int i = 1 ; i < n ; i++) {
			//~ if(protocol[i] == 0) {
				//~ add_edge(i, host[i]);
			//~ } else if(protocol[i] == 1) {
				//~ for(int x = 0 ; x < n ; x++)
					//~ if(G[host[i]][x])
						//~ add_edge(x, i);
			//~ } else {
				//~ for(int x = 0 ; x < n ; x++)
					//~ if(G[host[i]][x])
						//~ add_edge(x, i);
				//~ add_edge(i, host[i]);
			//~ }
		//~ }
		
		//~ int res = 0;
		//~ for(int mask = 0 ; mask < (1 << n) ; mask++) {
			//~ int sum = 0;
			//~ bool ok = true;
			//~ for(int i = 0 ; i < n ; i++) {
				//~ if(mask & (1 << i)) {
					//~ sum += confidence[i];
					//~ for(int j = i + 1 ; j < n ; j++) {
						//~ if(mask & (1 << j)) {
							//~ if(G[i][j])
								//~ ok = false;
						//~ }
					//~ }
				//~ }
			//~ }
			//~ if(ok)
				//~ res = max(res, sum);
		//~ }
		
		//~ return res;
	//~ }
	
	//~ if(subtask[2]) {
		//~ int sum = 0;
		//~ for(int i = 0 ; i < n ; i++)
			//~ sum += confidence[i];
		//~ return sum;
	//~ }
	
	//~ if(subtask[3]) {
		//~ int maxv = 0;
		//~ for(int i = 0 ; i < n ; i++)
			//~ maxv = max(maxv, confidence[i]);
		//~ return maxv;
	//~ }
	
	//~ if(subtask[4]) {
		//~ c.resize(n);
		//~ for(int i = 0 ; i < n ; i++)
			//~ c[i] = confidence[i];
		//~ for(int i = 1 ; i < n ; i++)
			//~ ch[host[i]].push_back(i);
		//~ dfs(0);
		//~ return max(dp[0][0], dp[0][1]);
	//~ }
	
	if(subtask[5]) {
		memset(match, -1, sizeof match);
		for(int i = 1 ; i < n ; i++) {
			if(protocol[i] == 0) {
				clr[i] = (1 - clr[host[i]]);
				add_edge2(i, host[i]);
			} else {
				clr[i] = clr[host[i]];
				for(int x : GG[host[i]])
					add_edge2(i, x);
			}
		}
		
		int cnt = 0;
		for(int i = 0 ; i < n ; i++) {
			if(!clr[i]) {
				viscnt++;
				cnt += dfs2(i);
			}
			
			//~ cout << i << " " << clr[i] << " " << match[i] << " " << cnt << endl;
		}
		
		return n - cnt;
	}
	
	return -1;
}

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