Submission #1064441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064441		damjandavkov	Friend (IOI14_friend)	C++17	100 / 100	26 ms	7516 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int findSample(int n, int f[], int pa[], int ty[])
{
    int i, s = 0, m = 0, c;
    for (i = 0; i < n; i++)
    {
        s += f[i];
        m = max(m, f[i]);
    }
    vector<int> dp(n, 0), dq(n, 0);
    vector<vector<int> > v(n);
    for (i = 1; i < n; i++)
        v[pa[i]].push_back(i);
    for (i = n - 1; i >= 0; i--)
    {
        s = 0;
        for (auto h : v[i])
        {
            dq[i] += dq[h];
            if (!ty[h])
                s += dp[h];
        }
        m = s;
        c = s;
        for (auto h : v[i])
        {
            if (ty[h] == 1)
                c += dp[h];
            else if (!ty[h])
                c -= dp[h];
            else
                m = max(m, c + dp[h]);
            m = max(m, c);
        }
        m = max(m, f[i] + c);
        dq[i] += s;
        dp[i] = m - s;
        dp[i] = max(dp[i], 0);
    }
    return dq[0] + dp[0];
}

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