Submission #313615

#	Time	Username	Problem	Language	Result	Execution time	Memory
313615		amunduzbaev	Friend (IOI14_friend)	C++14	46 / 100	43 ms	4216 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;
int dp[1005][2], conf[200005];
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]);
}
int findSample(int n,int c[],int h[],int p[]){
    vector<int>v[n];
    int ans=0;
    for(int i=0;i<n;i++) conf[i]=c[i];
    if(n<=10){
        for(int i=1;i<n;i++){
            if(p[i]==0){
                v[h[i]].pb(i);
                v[i].pb(h[i]);
            }
            else {
                if(p[i]==2){
                    v[h[i]].pb(i);
                    v[i].pb(h[i]);
                }
                for(auto x:v[h[i]]){
                    v[x].pb(i);
                    v[i].pb(x);
                }
            }
        }
        int i=1;
        while(i < (1<<n)){
            int cost=0;
            vector<bool>used(n,0);
            for(int j=0;j<n;j++){
                if(!((1<<j)&i)) continue;
                bool t=true;
                for(auto x:v[j]) if(used[x]) t=false;
                if(t){
                    cost+=c[j];
                    used[j]=true;
                }
            }
            ans=max(ans,cost);
            i++;
        }
    }
    else if(p[1]==2){
        for(int i=0;i<n;i++){
                ans = max(ans, c[i]);
		}
    }
    else if(p[1]==1){
        for(int i=0;i<n;i++){
            ans+=c[i];
        }
    }
    else {
        edges.resize(n);
		for(int i=1;i<n;i++){
            edges[h[i]].pb(i);
            edges[i].pb(h[i]);
		}
		dfs(0,0);
		ans=max(dp[0][0],dp[0][1]);
	}

	return ans;
}

/*

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

*/

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