Submission #1102968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102968		alexander707070	Friend (IOI14_friend)	C++14	27 / 100	42 ms	32360 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];
int mins,maxs;

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;
    }
}

long long dp[MAXN][2];
bool vis[MAXN][2];

long long ff(int x,int p,int parent){
    if(vis[x][p])return dp[x][p];
    vis[x][p]=true;

    if(p==0){
        dp[x][p]=cost[x];
        for(int i:v[x]){
            if(i==parent)continue;
            dp[x][p]+=ff(i,1,x);
        }
    }

    long long sum=0;
    for(int i:v[x]){
        if(i==parent)continue;
        sum+=ff(i,0,x);
    }

    dp[x][p]=max(dp[x][p],sum);
    return dp[x][p];
}


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];

    mins=3; maxs=0;
    for(int i=1;i<=n-1;i++){
        mins=min(mins,protocol[i]);
        maxs=max(maxs,protocol[i]);
    }

    if(mins==maxs and mins==1){
        for(int i=0;i<n;i++)ans+=cost[i];
        return ans;
    }else if(mins==maxs and mins==2){
        for(int i=0;i<n;i++)ans=max(ans,cost[i]);
        return ans;
    }

    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);
            }
        }
    }

    if(n<=20){
        brute(n-1,0);
        return ans;
    }else if(mins==maxs==0){
        return ff(0,0,-1);
    }
    
    return 1/0;
}


/*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;
}*/

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:97:18: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   97 |     }else if(mins==maxs==0){
      |              ~~~~^~~~~~
friend.cpp:101:13: warning: division by zero [-Wdiv-by-zero]
  101 |     return 1/0;
      |            ~^~

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