Submission #666206

#	Time	Username	Problem	Language	Result	Execution time	Memory
666206		sofija6	Traffic (IOI10_traffic)	C++14	100 / 100	1034 ms	170808 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
#define ll long long
#define MAXN 1000010
using namespace std;
vector<ll> G[MAXN];
ll dp[MAXN],par[MAXN],num[MAXN];
void DFS(ll i)
{
    dp[i]=num[i];
    for (ll next : G[i])
    {
        if (next!=par[i])
        {
            par[next]=i;
            DFS(next);
            dp[i]+=dp[next];
        }
    }
}
int LocateCentre(int N, int pp[], int S[], int D[])
{
    for (ll i=0;i<N;i++)
        num[i]=pp[i];
    for (ll i=0;i<N-1;i++)
    {
        G[S[i]].push_back(D[i]);
        G[D[i]].push_back(S[i]);
    }
    par[0]=-1;
    DFS(0);
    ll ans=LLONG_MAX;
    int ind;
    for (ll i=0;i<N;i++)
    {
        ll cur=0;
        for (ll next : G[i])
        {
            if (next==par[i])
                cur=max(cur,dp[0]-dp[i]);
            else
                cur=max(cur,dp[next]);
        }
        if (cur<ans)
        {
            ans=cur;
            ind=i;
        }
    }
    return ind;
}

Compilation message (stderr)

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

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