Submission #745269

#	Time	Username	Problem	Language	Result	Execution time	Memory
745269		delrey	Friend (IOI14_friend)	C++14	19 / 100	4 ms	5096 KiB

friend

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

using namespace std;

vector <int> v[100000];
int height[100000];
vector <int> level[100000];
int dp[100000][2];

int findSample(int n, int confidence[], int host[], int protocol[])
{
    level[0].push_back(0);
    for(int i = 1; i < n; i++)
    {
        v[host[i]].push_back(i);
        height[i] = height[host[i]] + 1;
        level[height[i]].push_back(i);
    }
    //cout<<"BBB"<<endl;
    for(int i = n - 1; i >= 0; i--)
    {
        //cout<<"i: "<<i<<endl;
        for(auto j : level[i])
        {
            dp[j][0] = confidence[j];
            for(auto t : v[j])
                dp[j][0] += dp[t][1];
            dp[j][1] = 0;
            for(auto t : v[j])
                dp[j][1] += max(dp[t][0], dp[t][1]);
        }
    }
    //cout<<"CCC"<<endl;
    int res = max(dp[0][0], dp[0][1]);
    return res;
}

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