Submission #355518

#	Time	Username	Problem	Language	Result	Execution time	Memory
355518		Mefarnis	Friend (IOI14_friend)	C++14	46 / 100	40 ms	6380 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define maxn 1000
#define pb push_back
using namespace std;

int n;
int dp[maxn][2];
bool mat[maxn][maxn];
vector<int> scores;
vector<int> adj[maxn];

int solve1() {
	int res = 0;
	int N = (1<<n);
	for( int bmask = 1 ; bmask < N ; bmask++ ) {
		int sum = 0;
		vector<int> vec;
		for( int i = 0 ; i < n ; i++ )
			if(bmask&(1<<i)) {
				vec.pb(i);
				sum += scores[i];
			}
		int sz = vec.size();
		bool ok = true;
		for( int i = 0 ; i < sz ; i++ )
			for( int j = 0 ; j < sz ; j++ ) {
				int u = vec[i];
				int v = vec[j];
				if(mat[u][v])
					ok = false;
			}
		if(ok)
			res = max(res,sum);
	}
	return res;
}

int solve2() {
	int sum = 0;
	for( int i = 0 ; i < n ; i++ )
		sum += scores[i];
	return sum;
}

int solve3() {
	int mx = 0;
	for( int i = 0 ; i < n ; i++ )
		mx = max(mx,scores[i]);
	return mx;
}

int f(int u , int st , int dad) {
	if(dp[u][st] != -1)
		return dp[u][st];
	dp[u][st] = 0;
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i];
		if(v != dad)
			dp[u][st] += f(v,1,u);
	}
	if(st) {
		int sum = scores[u];
		for( int i = 0 ; i < deg ; i++ ) {
			int v = adj[u][i];
			if(v != dad)
				sum += f(v,0,u);
		}
		dp[u][st] = max(dp[u][st],sum);
	}
	return dp[u][st];
}

int solve4() {
	memset(dp,-1,sizeof(dp));
	return f(0,1,-1);
}

int findSample(int N, int score[], int host[], int type[]) {
	n = N;
	int ans = 0;
	scores.pb(score[0]);
	for( int i = 1 ; i < N ; i++ ) {
		scores.pb(score[i]);
		int u = host[i];
		if(type[i] == 0) {
			adj[i].pb(u);
			adj[u].pb(i);
			mat[u][i] = mat[i][u] = true;
		}
		else if(type[i] == 1) {
			int deg = adj[u].size();
			for( int j = 0 ; j < deg ; j++ ) {
				int to = adj[u][j];
				adj[i].pb(to);
				adj[to].pb(i);
				mat[to][i] = mat[i][to] = true;
			}
		}
		else {
			int deg = adj[u].size();
			for( int j = 0 ; j < deg ; j++ ) {
				int to = adj[u][j];
				adj[i].pb(to);
				adj[to].pb(i);
				mat[to][i] = mat[i][to] = true;
			}
			adj[i].pb(u);
			adj[u].pb(i);
			mat[u][i] = mat[i][u] = true;
		}
	}
	if(n <= 10)
		ans = solve1();
	else if(type[1] == 1)
		ans = solve2();
	else if(type[1] == 2)
		ans = solve3();
	else if(type[1] == 0)
		ans = solve4();
	return ans;
}

/*
int main() {
	
	return 0;
}
*/

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