Submission #1064402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064402		damjandavkov	Friend (IOI14_friend)	C++17	69 / 100	16 ms	2736 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int findSample(int n, int f[], int pa[], int ty[])
{
    if (n < 11)
    {
    vector<vector<bool> > vg(n, vector<bool>(n, 0));
    int i, j, k, s, ms = 0;
    for (i = 1; i < n; i++)
    {
        k = pa[i];
        if (ty[i] != 1)
            vg[i][k] = vg[k][i] = 1;
        if (ty[i])
        {
            for (j = 0; j < i; j++)
            {
                if (vg[j][k])
                    vg[i][j] = vg[j][i] = 1;
            }
        }
    }
    for (i = 0; i < (1 << n); i++)
    {
        s = 0;
        for (j = 0; j < n; j++)
        {
            if (i & (1 << j))
                s += f[j];
        }
        for (j = 0; j < n; j++)
        {
            for (k = 0; k < n; k++)
            {
                if ((i & (1 << j)) && (i & (1 << k)) && vg[j][k])
                    s = 0;
            }
        }
        ms = max(ms, s);
    }
	return ms;
    }
    int i, s = 0, m = 0, c1, c2;
    for (i = 0; i < n; i++)
    {
        s += f[i];
        m = max(m, f[i]);
    }
    if (ty[1] == 2)
        return m;
    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;
        c1 = c2 = 0;
        for (auto h : v[i])
        {
            if (ty[h])
                c2 += dp[h];
            else
                c1 += dp[h];
            m = max(m, c2 + s - c1);
        }
        m = max(m, f[i] + c2);
        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: 0 / 31