Submission #313688

#	Time	Username	Problem	Language	Result	Execution time	Memory
313688		amunduzbaev	Friend (IOI14_friend)	C++14	46 / 100	307 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 t){
    used[ei]=t;
    for(auto x : edges[ei]){
        if(match[x]==-1||used[match[x]]!=t&&check(match[x],t)){
            match[x]=ei;
            return true;
        }
    }
    return false;
}
//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{
        v.resize(1005);
        for(int i=1;i<n;i++){
            if(p[i]==0){
                edges[h[i]].pb(i);
                edges[i].pb(h[i]);
            }
            else {
                for(auto x:edges[h[i]]){
                    edges[x].pb(i);
                    edges[i].pb(x);
                }
                if(p[i]==2){
                    edges[h[i]].pb(i);
                    edges[i].pb(h[i]);
                }
            }
        }
        for(int i=0;i<n;i++)
            if(!used[i]) bpart(i,0);
        /*
        for(auto x:l) cout<<x<<" ";
        cout<<'\n';
        for(auto x:r) cout<<x<<" ";
        cout<<'\n';
        */
        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 time=0;
        for(auto ei:l){
            time++;
            ans += check(ei,time);
        }
        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]]!=t&&check(match[x],t)){
      |                          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:135:21: warning: statement has no effect [-Wunused-value]
  135 |             match[i]-1;
      |             ~~~~~~~~^~

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