Submission #206978

#	Time	Username	Problem	Language	Result	Execution time	Memory
206978		joylintp	Traffic (IOI10_traffic)	C++17	100 / 100	1802 ms	242100 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;

bool vis[1000000];
long long val[1000000], sum;
set<int> edge[1000000];

void dfs(int k)
{
    vis[k] = true;
    for (int i : edge[k])
        if (!vis[i])
            edge[i].erase(k), dfs(i), val[k] += val[i];
}

int LocateCentre(int N, int pp[], int S[], int D[])
{
    for (int i = 0; i < N; i++)
        val[i] = pp[i], sum += val[i];
    for (int i = 0; i < N - 1; i++)
        edge[S[i]].insert(D[i]), edge[D[i]].insert(S[i]);
    dfs(0);

    int ret;
    long long mn = 1e18;
    for (int i = 0; i < N; i++)
    {
        long long mx = 0;
        for (int j : edge[i])
            mx = max(mx, val[j]);
        mx = max(mx, sum - val[i]);

        if (mx < mn)
            mn = mx, ret = i;
    }
    return ret;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:37:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret;
            ^~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25