Submission #46321

#	Time	Username	Problem	Language	Result	Execution time	Memory
46321		RayaBurong25_1	Beads and wires (APIO14_beads)	C++14	100 / 100	256 ms	17900 KiB

beads

#include <stdio.h>
#include <vector>
#define INF 2000000007
std::vector<std::pair<int, int> > AdjList[200005];
int Black[200005];
int White[200005];
int max(int a, int b)
{
    return (a > b)?a:b;
}
void dfsSub(int u, int pa)
{
    int i, v, s = AdjList[u].size();
    // White[u] = -INF;
    Black[u] = -INF;
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].first;
        if (v != pa)
        {
            dfsSub(v, u);
            White[u] += max(Black[v] + AdjList[u][i].second, White[v]);
        }
    }
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].first;
        if (v != pa)
        {
            Black[u] = max(Black[u], White[u] - max(Black[v] + AdjList[u][i].second, White[v]) + AdjList[u][i].second + White[v]);
        }
    }
    // printf("u%d w%d b%d\n", u, White[u], Black[u]);
}
int Ans = 0;
void dfs(int u, int pa, int B, int W, int C)
{
    int i, v, s = AdjList[u].size();
    int R = White[u] + max(W, B + C);
    // printf("u%d R%d\n", u, R);
    int S, P = 0, Pi, Q = 0, Qi;
    Ans = max(Ans, R);
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].first;
        if (v != pa)
        {
            S = R - max(White[v], Black[v] + AdjList[u][i].second) + AdjList[u][i].second + White[v];
            if (S >= P)
            {
                Q = P; Qi = Pi;
                P = S; Pi = v;
            }
            else if (S >= Q)
            {
                Q = S; Qi = v;
            }
        }
        else
        {
            S = R - max(W, B + C) + C + W;
            if (S >= P)
            {
                Q = P; Qi = Pi;
                P = S; Pi = v;
            }
            else if (S >= Q)
            {
                Q = S; Qi = v;
            }
        }
    }
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].first;
        if (v != pa)
        {
            if (v == Pi)
                dfs(v, u, Q - max(White[v], Black[v] + AdjList[u][i].second), R - max(White[v], Black[v] + AdjList[u][i].second), AdjList[u][i].second);
            else
                dfs(v, u, P - max(White[v], Black[v] + AdjList[u][i].second), R - max(White[v], Black[v] + AdjList[u][i].second), AdjList[u][i].second);
        }
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    int i, a, b, c;
    for (i = 0; i < N - 1; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        AdjList[a].push_back({b, c});
        AdjList[b].push_back({a, c});
    }
    dfsSub(1, 0);
    dfs(1, 0, 0, 0, 0);
    printf("%d", Ans);
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int, int, int)':
beads.cpp:41:30: warning: variable 'Qi' set but not used [-Wunused-but-set-variable]
     int S, P = 0, Pi, Q = 0, Qi;
                              ^~
beads.cpp: In function 'int main()':
beads.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
beads.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int, int, int)':
beads.cpp:78:13: warning: 'Pi' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (v == Pi)
             ^~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43