Submission #1064322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064322		damjandavkov	Friend (IOI14_friend)	C++17	35 / 100	1 ms	600 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int findSample(int n, int v[], int pa[], int ty[])
{
    if (n < 1)
    {
    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 += v[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;
    for (i = 0; i < n; i++)
    {
        s += v[i];
        m = max(m, v[i]);
    }
    if (ty[1] == 1)
        return s;
    if (ty[1])
        return m;
    vector<int> dp(n, 0), dq(n, 0);
    for (i = n - 1; i >= 0; i--)
    {
        dp[i] += v[i];
        dp[i] = max(dp[i], dq[i]);
        if (i)
        {
            dq[pa[i]] += dp[i];
            dp[pa[i]] += dq[i];
        }
    }
    return dp[0];
}

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