Submission #775594

#	Time	Username	Problem	Language	Result	Execution time	Memory
775594		DobromirAngelov	Traffic (IOI10_traffic)	C++14	0 / 100	14 ms	23820 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 dfs(int v,int par)
{
    subtr[v]=a[v];
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par) continue;
        subtr[v]+=dfs(adj[v][i], v);
    }
    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]);
    }

    dfs(0,-1);

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

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