Submission #313685

#	Time	Username	Problem	Language	Result	Execution time	Memory
313685		amunduzbaev	친구 (IOI14_friend)	C++14	27 / 100	45 ms	8568 KiB

friend

//#include "grader.cpp"
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(n) push_back(n)
vector<vector<int>>edges;
const int N=1e5+5;
int dp[N][2], conf[N], used[N], match[N];
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]);
}
vector<vector<int>>v;
vector<int>l,r;
void add(int a,int b){
    v[a].pb(b);
    v[b].pb(a);
}
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);
    }
}
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;
}
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){
        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> used(n,0);
            for(int i=0;i<n;i++){
                if(!((1<<i)&mask)) continue;
                bool ok=1;
                for(auto x:v[i]) if(used[x]) ok=0;
                if(ok){
                    cost+=c[i];
                    used[i]=1;
                }
            }
            ans=max(ans,cost);
            mask++;
        }
        return ans;
    }else if(e1){
		for(int i=0;i<n;i++) ans += c[i];
	}else if(e2){
		for(int i=0;i<n;i++) ans = max(ans, c[i]);
	}else if(e0){
		for(int i=1;i<n;i++){
			edges[i].pb(h[i]);
			edges[h[i]].pb(i);
		}
		dfs(0, 0);
		ans = max(dp[0][0], dp[0][1]);
	}
	else{
	    v.resize(n);
        for(int i=1;i<n;i++){
            if(p[i]==0){
                add(h[i],i);
                edges[h[i]].pb(i);
                edges[i].pb(h[i]);
            }
            else {
                for(auto x:v[h[i]]){
                    add(h[i],i);
                    edges[x].pb(i);
                    edges[i].pb(x);
                }
                if(p[i]==2){
                    add(h[i],i);
                    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<<" ";

        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 0 1 2 0
0 0 1 2 1 0

*/

Compilation message (stderr)

friend.cpp: In function 'bool check(int, int)':
friend.cpp:37:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |         if(match[x]==-1||used[match[x]]!=t&&check(match[x],t)){
      |                          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:125:21: warning: statement has no effect [-Wunused-value]
  125 |             match[i]-1;
      |             ~~~~~~~~^~

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