Submission #775596

#	Time	Username	Problem	Language	Result	Execution time	Memory
775596		DobromirAngelov	Traffic (IOI10_traffic)	C++14	100 / 100	949 ms	174616 KiB

traffic

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

using namespace std;

const int MAXN=1e6+5;
const int INF=2e9+5;

int a[MAXN];
vector<int> adj[MAXN];
int subtr[MAXN];
int par[MAXN];

int dfs(int v)
{
    subtr[v]=a[v];
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par[v]) continue;
        par[adj[v][i]]=v;
        subtr[v]+=dfs(adj[v][i]);
    }
    return subtr[v];
}

int LocateCentre(int n,int w[],int u[],int v[])
{
    for(int i=0;i<n;i++) a[i]=w[i];
    for(int i=0;i<n-1;i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    par[0]=-1;
    dfs(0);

    int ans=-1, best=INF;
    for(int i=0;i<n;i++)
    {
        int curMax=subtr[0]-subtr[i];
        for(int j=0;j<adj[i].size();j++)
        {
            if(adj[i][j]==par[i]) continue;
            curMax=max(curMax, subtr[adj[i][j]]);
        }
        if(curMax<best)
        {
            best=curMax;
            ans=i;
        }
    }

    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'int dfs(int)':
traffic.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j=0;j<adj[i].size();j++)
      |                     ~^~~~~~~~~~~~~~

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