提出 #20159067

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

const int maxN = 200009;
int N, dp[maxN], vol[maxN], t[maxN], curr[maxN];
vector < int > v[maxN];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=2; i<=N; i++)
    scanf ("%d", &t[i]), v[t[i]].push_back (i);
for (int i=N; i>=1; i--)
    vol[i] ++, vol[t[i]] += vol[i];
for (int i=N; i>=1; i--)
{
    ///dp[i] = solution to subtree i
    dp[i] = 1;
    int unwantedControlKeptDp = 0, unwantedControlKeptVolDp = 0;
    int K = 0;
    for (auto j : v[i])
        if (vol[j] % 2 == 0)
        {
            if (vol[j] - dp[j] > dp[j])
                dp[i] += dp[j]; ///aoki wins out of these and he can force me at the very beginning to take them
            else
            {
                ///these are unwanted: because the controller loses and keeps control, so will be taken in the end
                unwantedControlKeptDp += dp[j]; ///better one for the one who is not controller
                unwantedControlKeptVolDp += vol[j] - dp[j];
            }
        }
        else
        {
            ///I can keep precisely [(K + 1) / 2] of these
            dp[i] += vol[j] - dp[j]; ///pretend all go for Tak
            curr[++K] = dp[j] - (vol[j] - dp[j]);
        }
    if (K % 2 == 0) dp[i] += unwantedControlKeptDp; ///bad for Aoki who stays controller in the end
    else dp[i] += unwantedControlKeptVolDp;

    sort (curr + 1, curr + K + 1);
    for (int j=1; j<=K; j+=2)
        dp[i] += curr[j];
}

printf ("%d\n", dp[1]);
return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   14 | scanf ("%d", &N);
      | ~~~~~~^~~~~~~~~~
./Main.cpp:16:11: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   16 |     scanf ("%d", &t[i]), v[t[i]].push_back (i);
      |     ~~~~~~^~~~~~~~~~~~~

ジャッジ結果