Submission #782037

#	Time	Username	Problem	Language	Result	Execution time	Memory
782037		I_Love_EliskaM_	Friend (IOI14_friend)	C++14	46 / 100	25 ms	1484 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
const int inf=1e9;


const int N=1e3+5;
int adj[N][N];
int vis[N];
vector<int> g[N];
int c[N];
int a[N];
int dp[N][2];

int dfs(int u) {
	int r=a[u];
	vis[u]=1;
	forn(i,N) if (adj[u][i]) {
		if (vis[i]) continue;
		c[i]=c[u]^1;
		r+=dfs(i);
	}	
	return r;
}
int sum(int u) {
	int r=c[u]*a[u];
	vis[u]=2;
	forn(i,N) if (adj[u][i]) {
		if (vis[i]==2) continue;
		r+=sum(i);
	}	
	return r;
}

void dfs(int u, int p) {
	dp[u][1]=a[u];
	for(auto&v:g[u]) {
		dfs(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0];
	}
}

int findSample(int n, int c[], int h[], int p[]) {
	if (n>1000) return 0;
	forn(i,n) a[i]=c[i];
	if (n<=10) {
		for (int i=1; i<n; ++i) {
			if (p[i]) {
				forn(j,n) if (adj[h[i]][j]) adj[i][j]=adj[j][i]=1;
			}
			if (p[i]%2==0) {
				adj[h[i]][i]=adj[i][h[i]]=1;
			} 
		}
		int ans=0;
		forn(mask,1<<n) {
			vector<int> v;
			forn(i,n) if ((mask>>i)&1) v.pb(i);
			int f=0, s=0;
			for(auto&x:v) for(auto&y:v) f|=adj[x][y];
			for(auto&x:v) s+=a[x];
			if (!f) ans=max(ans,s);
		}
		return ans;
	}
	int z; 

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==1;
	if (z) {
		int s=0; forn(i,n) s+=a[i]; return s;
	}

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==2;
	if (z) {
		int s=0; forn(i,n) s=max(s,a[i]); return s;
	}

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==0;
	if (z) {
		for(int i=1; i<n; ++i) {
			g[h[i]].pb(i);
		}
		dfs(0,-1);
		return max(dp[0][0],dp[0][1]);
	}

	int ans=0;
	forn(i,n) {
		if (vis[i]) continue;
		int sz=dfs(i);
		int x=sum(i);
		ans+=max(sz-x,x);
	}
	return ans;

}

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