Submission #356375

#	Time	Username	Problem	Language	Result	Execution time	Memory
356375		Mefarnis	Friend (IOI14_friend)	C++14	46 / 100	1088 ms	6892 KiB

friend

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

int n;
int cntg[2];
int tc[maxn];
int col[maxn];
int bef[maxn];
int dp[maxn][2];
int G[maxn][maxn];
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);
}

void dfs(int u) {
	cntg[col[u]]++;
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i];
		if(col[v] == -1) {
			col[v] = !col[u];
			dfs(v);
		}
	}
}

int bfs(int bfscnt) {
	queue<int> Q;
	Q.push(0);
	tc[0] = bfscnt;
	while(!Q.empty()) {
		int u = Q.front();
		for( int v = 0 ; v <= n+1 ; v++ )
			if(tc[v] != bfscnt) {
				Q.push(v);
				bef[v] = u;
				tc[v] = bfscnt;
			}
	}
}

int solve5() {
	memset(col,-1,sizeof(col));
	for( int i = 0 ; i < n ; i++ )
		if(col[i] == -1) {
			col[i] = 0;
			dfs(i);
		}
	for( int i = 0 ; i < n ; i++ ) {
		if(col[i] == 0)
			G[0][i+1] = 1;
		else
			G[i+1][n+1] = 1;
		for( int j = i+1 ; j < n ; j++ )
			if(mat[i][j]) {
				if(col[i] == 0)
					G[i+1][j+1] = 1;
				else
					G[j+1][i+1] = 1;
			}
	}
	int cntbfs = 0;
	int res = n , p;
	while(p = bfs(++cntbfs)) {
		res -= p;
		int u = n+1;
		while(u != 0) {
			int v = bef[u];
			G[v][u] -= p;
			G[u][v] += p;
			u = v;
		}
	}
	return res;
}

int findSample(int N, int score[], int host[], int type[]) {
	n = N;
	int ans = 0;
	int bmask = 0;
	scores.pb(score[0]);
	for( int i = 1 ; i < N ; i++ ) {
		scores.pb(score[i]);
		int u = host[i];
		bmask |= (1<<type[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(bmask == 2)
		ans = solve2();
	else if(bmask == 4)
		ans = solve3();
	else if(bmask == 1)
		ans = solve4();
	else if(bmask == 3)
		ans = solve5();
	return ans;
}

/*
int main() {
	int n = 10;
	int score[n] = {1,1,1,1,1,1,1,1,1,1};
	int host[n] = {0,0,0,0,0,0,0,0,0,0};
	int type[n] = {0,0,0,0,0,0,0,0,0,1};
	printf("%d\n",findSample(n,score,host,type));
	return 0;
}*/

Compilation message (stderr)

friend.cpp: In function 'int bfs(int)':
friend.cpp:110:1: warning: no return statement in function returning non-void [-Wreturn-type]
  110 | }
      | ^
friend.cpp: In function 'int solve5()':
friend.cpp:134:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  134 |  while(p = bfs(++cntbfs)) {
      |        ~~^~~~~~~~~~~~~~~

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