Submission #313690

#	Time	Username	Problem	Language	Result	Execution time	Memory
313690		amunduzbaev	Friend (IOI14_friend)	C++14	69 / 100	320 ms	65536 KiB

friend

//#include "grader.cpp"
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(n) push_back(n)

const int N=1e5+5;
int dp[N][2], conf[N], used[N], match[N];
vector<vector<int>>v;
vector<int>l, r, edges[1005];
void add(int a,int b){
    v[a].pb(b);
    v[b].pb(a);
}
//if all 0
void dfs(int ei,int prev){
    dp[ei][1]=conf[ei];
    for(auto x : edges[ei]){
        if(x == prev) continue;
        dfs(x,ei);
        dp[ei][0] += dp[x][1];
        dp[ei][1] += dp[x][0];
    }
    dp[ei][1]=max(dp[ei][0],dp[ei][1]);
}
//divide into two part left and right and solve with bipartite
void bpart(int ei, int col=0){
	if(col == 0) l.pb(ei);
	else r.pb(ei);
	used[ei] = true;
	for(auto x : edges[ei]){
		if(used[x])continue;
		bpart(x, col^1);
	}
}
//check if matches
bool check(int ei, int time){
	used[ei]=time;
	for(auto x : edges[ei]){
		if(match[x]==-1 || used[match[x]]!=time && check(match[x], time)) {
			match[x]=ei;
			return 1;
		}
	}return 0;
}
//main function
int findSample(int n,int c[],int h[],int p[]){
    int ans=0;
    for(int i=0;i<n;i++){
        conf[i]=c[i];
    }
    bool e0=1, e1=1, e2=1;
    for(int i=1;i<n;i++){
        e0=(p[i]!=0?0:e0);
        e1=(p[i]!=1?0:e1);
        e2=(p[i]!=2?0:e2);
    }
    // if n <= 15
    if(n<=15){
        v.resize(n);
        for(int i=1;i<n;i++){
            if(p[i]==0) add(h[i],i);
            else{
                for(auto x:v[h[i]]) add(x,i);
                if(p[i]==2) add(h[i],i);
            }
        }
        int mask=1;
        while(mask < (1<<n)){
            int cost=0;
            vector<int> used1(n,0);
            for(int i=0;i<n;i++){
                if(!((1<<i)&mask)) continue;
                bool ok=1;
                for(auto x:v[i]) if(used1[x]) ok=0;
                if(ok){
                    cost+=c[i];
                    used1[i]=1;
                }
            }
            ans=max(ans,cost);
            mask++;
        }
        return ans;
    }
    // if all 1
    else if(e1){
		for(int i=0;i<n;i++) ans += c[i];
	}
    // if all 2
	else if(e2){
		for(int i=0;i<n;i++) ans = max(ans, c[i]);
	}
	// if all 0
	else if(e0){
		for(int i=1;i<n;i++){
			edges[i].pb(h[i]);
			edges[h[i]].pb(i);
		}
		dfs(0, 0);
		ans = dp[0][1];
	}
    // if 1 and 0
	else {
		for(int i=1;i<n;i++){
			if(p[i] == 0){
				edges[i].pb(h[i]);
				edges[h[i]].pb(i);
			}else {
				for(auto x : edges[h[i]]){
					edges[i].pb(x);
					edges[x].pb(i);
				}
				if(p[i] == 2){
					edges[i].pb(h[i]);
					edges[h[i]].pb(i);
				}
			}
		}
		for(int i=0;i<n;i++) if(!used[i])bpart(i);
		int s = 1001, e = 1002;
		for(auto x : l) edges[s].pb(x);
		for(auto x : r) edges[x].pb(e);
		for(int i=0;i<n;i++) match[i] = -1;
		int timer = 0;
		for(auto ei : l){
			timer++;
			ans += check(ei, timer);
		}ans = n-ans;
	}
	return ans;
}

/*

6
13 3 6 20 10 15
0 0 1 1 2 0
0 0 1 1 1 0

*/

Compilation message (stderr)

friend.cpp: In function 'bool check(int, int)':
friend.cpp:40:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |   if(match[x]==-1 || used[match[x]]!=time && check(match[x], time)) {
      |                      ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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