Submission #463496

#	Time	Username	Problem	Language	Result	Execution time	Memory
463496		BT21tata	Traffic (IOI10_traffic)	C++17	100 / 100	1169 ms	168260 KiB

traffic

#include<bits/stdc++.h>
#include "traffic.h"

using namespace std;

vector<int> g[1000005];
int par[1000005], dis[1000005];

void dfs(int v, int p)
{
    for(int u : g[v])
        if(u!=p) par[u]=v, dfs(u, v), dis[v]+=dis[u];
}

int LocateCentre(int n, int p[], int S[], int D[])
{
    int ans=2000000000, cen;
    for(int i=0; i<n-1; i++)
    {
        g[S[i]].push_back(D[i]);
        g[D[i]].push_back(S[i]);
    }
    for(int i=0; i<n; i++)
        dis[i]=p[i];
    dfs(0, 0);

    for(int i=0; i<n; i++)
    {
        int cnt=0;
        for(int c : g[i])
        {
            if(c==par[i])
                cnt=max(cnt, dis[0]-dis[i]);
            else cnt=max(cnt, dis[c]);
        }
        if(cnt<ans) ans=cnt, cen=i;

    }
    return cen;
}

Compilation message (stderr)

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

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