Submission #585744

#	Time	Username	Problem	Language	Result	Execution time	Memory
585744		Hanksburger	Traffic (IOI10_traffic)	C++17	100 / 100	1058 ms	167600 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
int res[1000005], sz[1000005], sum;
vector<int> adj[1000005];
void dfs(int u, int p)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i];
        if (v==p)
            continue;
        dfs(v, u);
        res[u]=max(res[u], sz[v]);
        sz[u]+=sz[v];
    }
    res[u]=max(res[u], sum-sz[u]);
}
int LocateCentre(int n, int p[], int x[], int y[])
{
    for (int i=0; i<n; i++)
        sum+=sz[i]=p[i];
    for (int i=0; i<n-1; i++)
    {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    dfs(0, -1);
    int ind=0, mn=2e9;
    for (int i=0; i<n; i++)
    {
        if (mn>res[i])
        {
            mn=res[i];
            ind=i;
        }
    }
    return ind;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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