Submission #775381

#	Time	Username	Problem	Language	Result	Execution time	Memory
775381		boris_mihov	Friend (IOI14_friend)	C++17	19 / 100	2 ms	2772 KiB

friend

#include "friend.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
int c[MAXN];
int dp[MAXN][2];
bool bl[MAXN][2];
std::vector <int> g[MAXN];

int f(int node, bool can)
{
    if (bl[node][can])
    {
        return dp[node][can];
    }

    bl[node][can] = true;
    int sumTake = c[node];
    int sumNotTake = 0;

    for (const int &u : g[node])
    {
        sumTake += f(u, 0);
        sumNotTake += f(u, 1);
    }

    dp[node][can] = sumNotTake;
    if (can) dp[node][can] = std::max(dp[node][can], sumTake);
    return dp[node][can];
}

int findSample(int N, int confidence[], int host[], int protocol[])
{
    n = N;
    for (int i = 0 ; i < n ; ++i)
    {
        c[i] = confidence[i];
    }

    for (int i = 1 ; i < n ; ++i)
    {
        g[host[i]].push_back(i);
    }

    return f(0, 1);
}

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