제출 #93393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93393		Kastanda	Chase (CEOI17_chase)	C++11	100 / 100	774 ms	337272 KiB

chase

// Borrowed
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 1e5 + 5, K = 103;
int n, m, k, A[N], P[N];
long long S[N], dp[N][K][2], dp2[N][K][2], T[K][2][2];
vector < int > Adj[N];
void DFS(int v, int p)
{
    P[v] = p;
    for (int &u : Adj[v])
        if (u != p)
            S[v] += A[u];
    for (int &u : Adj[v])
        if (u != p)
        {
            DFS(u, v);
            for (int i = 0; i <= k; i++)
                dp[v][i][0] = max(dp[v][i][0], max(dp[u][i][1], dp[u][i][0]));
            for (int i = 1; i <= k; i++)
                dp[v][i][1] = max(dp[v][i][1], S[v] + max(dp[u][i-1][1], dp[u][i-1][0]));
        }
}
void DFS2(int v, int p)
{
    memset(T, 0, sizeof(T));
    for (int i = 1; i <= k; i++)
        T[i][0][0] = dp2[v][i][0], T[i][1][0] = dp2[v][i][1];
    for (int &u : Adj[v])
        if (u != p)
        {
            for (int i = 1; i <= k; i++)
            {
                long long val = max(dp[u][i][1] - A[v], dp[u][i][0]);
                if (T[i][0][1] < val)
                    T[i][0][1] = val;
                if (T[i][0][0] < T[i][0][1])
                    swap(T[i][0][0], T[i][0][1]);
            }
            for (int i = 1; i <= k; i++)
            {
                long long val = S[v] + A[P[v]] + max(dp[u][i-1][1] - A[v], dp[u][i-1][0]);
                if (T[i][1][1] < val)
                    T[i][1][1] = val;
                if (T[i][1][0] < T[i][1][1])
                    swap(T[i][1][1], T[i][1][0]);
            }
        }
    for (int &u : Adj[v])
        if (u != p)
        {
            for (int i = 1; i <= k; i++)
            {
                /// Chosen
                long long val = T[i][1][0];
                if (val == S[v] + A[P[v]] + max(dp[u][i-1][1] - A[v], dp[u][i-1][0]))
                    val = T[i][1][1];
                dp2[u][i][0] = val - A[u];
                /// Not
                val = T[i][0][0];
                if (val == max(dp[u][i][1] - A[v], dp[u][i][0]))
                    val = T[i][0][1];
                dp2[u][i][0] = max(dp2[u][i][0], val);
            }
            for (int i = 2; i <= k; i++)
            {
                /// Chosen
                long long val = T[i-1][1][0];
                if (val == S[v] + A[P[v]] + max(dp[u][i-2][1] - A[v], dp[u][i-2][0]))
                    val = T[i-1][1][1];
                dp2[u][i][1] = S[u] + A[v] + val - A[u];
                /// Not
                val = T[i-1][0][0];
                if (val == max(dp[u][i-1][1] - A[v], dp[u][i-1][0]))
                    val = T[i-1][0][1];
                dp2[u][i][1] = max(dp2[u][i][1], S[u] + A[v] + val);
            }
            dp2[u][1][1] = S[u] + A[v];
        }
    for (int &u : Adj[v])
        if (u != p)
            DFS2(u, v);
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1, v, u; i < n; i++)
        scanf("%d%d", &v, &u), Adj[v].pb(u), Adj[u].pb(v);
    DFS(1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            dp[i][j][1] += A[P[i]];
    DFS2(1, 0);
    long long Mx = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            for (int w = 0; w <= 1; w ++)
            {
                Mx = max(Mx, max(dp[i][j][w], dp2[i][j][w]));
                //printf("%d , %d : %lld\n", i, j, dp[i][j][0]);
            }
    printf("%lld", Mx);
    return (0);
}

컴파일 시 표준 에러 (stderr) 메시지

chase.cpp: In function 'int main()':
chase.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
chase.cpp:93:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u), Adj[v].pb(u), Adj[u].pb(v);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30