Submission #421611

#	Time	Username	Problem	Language	Result	Execution time	Memory
421611		Belgutei	Traffic (IOI10_traffic)	C++17	100 / 100	1162 ms	171684 KiB

traffic

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

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

vector<ll> v[1000005];
ll sum[1000005],val[1000005];
ll parent[1000005];
ll x[1000005];
bool visited[1000005];
ll ans=1e18;
ll node=0;

void dfs(int node){
   visited[node]=1;
   x[node]+=val[node];
   for(int i=0; i<v[node].size(); i++){
      if(visited[v[node][i]]==0){
         dfs(v[node][i]);
         parent[v[node][i]]=node;
         x[node]+=x[v[node][i]];
      }
   }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   int n=N;
   for(int i=0; i<n; i++){
      val[i]=pp[i];
   }
   for(int i=0; i<N-1; i++){
      v[S[i]].pb(D[i]);
      v[D[i]].pb(S[i]);
   }
   dfs(0);
   for(int i=0; i<n; i++){
      ll mx=0;
      for(int j=0; j<v[i].size(); j++){
         if(v[i][j]==parent[i]) continue;
         mx=max(mx,x[v[i][j]]);
      }
      mx=max(mx,x[0]-x[i]);
      if(mx<ans){
         ans=mx;
         node=i;
      }
   }
   return node;
}

Compilation message (stderr)

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

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