Submission #582914

#	Time	Username	Problem	Language	Result	Execution time	Memory
582914		sff_user	Traffic (IOI10_traffic)	C++17	100 / 100	1166 ms	174616 KiB

traffic

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

#define pb push_back
#define vi vector<int>
#define ll long long

using namespace std;

vector<vi > adj;
ll sub[1000006];
int par[1000006];
void dfs(int u , int p, int pp[]){
   sub[u] = pp[u];
   par[u] = p;
   for(int v : adj[u]){
      if(v== p) continue;
      dfs(v,u,pp);
      sub[u] += sub[v];
   }
}

int LocateCentre(int n, int pp[] , int S[], int D[]) {
   adj.resize(n+1);
   for(int i = 0 ; i < n-1 ; i++){
      adj[S[i]].pb(D[i]);
      adj[D[i]].pb(S[i]);
   }   
   dfs(0,-1,pp);
   ll a =1e9 ,b = 0,ans;
   for(int i = 0 ; i < n ; i++){
      b=0;
      for(int j : adj[i]){
         if(j != par[i]){
            b = max(b,sub[j]);
            continue;
         }
         b = max(b,sub[0]-sub[i]);
      }
      if( b <= a){
         a = b;
         ans = i;
      }
   }

   return ans;
}

// int main(){
//    int n = 5;
//    int pp[5] = {10,10,10,20,20};
//    int S[4] = {0,1,2,3};
//    int D[4] = {2,2,3,4};
//    cout << LocateCentre(n,pp,S,D) << endl;
// }

Compilation message (stderr)

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

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