Submission #1102961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102961		alexander707070	Friend (IOI14_friend)	C++14	11 / 100	1076 ms	32232 KiB

friend

#include<bits/stdc++.h>
#include "friend.h"

#define MAXN 500007
using namespace std;

int n;
vector<int> v[MAXN];
long long ans,cost[MAXN];

bool li[MAXN];

void brute(int x,long long res){
    if(x==-1){
        ans=max(ans,res);
        return;
    }

    brute(x-1,res);

    int br=0;
    for(int i:v[x]){
        if(li[i])br++;
    }

    if(br==0){
        li[x]=true;
        brute(x-1,res+cost[x]);
        li[x]=false;
    }
}

int findSample(int N,int confidence[],int host[],int protocol[]){
//int findSample(int N,vector<int> confidence,vector<int> host,vector<int> protocol){
	n=N;

    for(int i=0;i<n;i++)cost[i]=confidence[i];

    for(int i=1;i<=n-1;i++){
        if(protocol[i]==0 or protocol[i]==2){
            v[host[i]].push_back(i);
            v[i].push_back(host[i]);
        }
        
        if(protocol[i]==1 or protocol[i]==2){
            for(int f:v[host[i]]){
                v[f].push_back(i);
                v[i].push_back(f);
            }
        }
    }

    brute(n-1,0);
    return ans;
}


/*int main(){

    cout<<findSample(6,{13,3,6,20,10,15},{0,0,0,1,2,0},{0,0,1,2,1,0})<<"\n";

	return 0;
}*/

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