Submission #820022

#	Time	Username	Problem	Language	Result	Execution time	Memory
820022		nemethm	Traffic (IOI10_traffic)	C++17	100 / 100	1008 ms	170884 KiB

traffic

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

using namespace std;

using ll = long long int;

vector<int> g[1000100];

ll subsum[1000100] = {0};
int ans = 0; ll optimal = numeric_limits<ll>::max();

void dfs(int node, int prev = -1){
   for(auto i : g[node]){
      if(i != prev){
         dfs(i, node);
         subsum[node] += subsum[i];
      }
   }
}

void solve(int node, int prev = -1){
   ll maxsubtree = subsum[0] - subsum[node];
   for(auto i : g[node]){
      if(i != prev){
         maxsubtree = max(maxsubtree, subsum[i]);
         solve(i, node);
      }
   }
   if(maxsubtree < optimal){
      optimal = maxsubtree;
      ans = node;
   }
}


int LocateCentre(int N, int pp[], int S[], int D[]) {
   for(int i = 0; i < N - 1; ++i){
      g[S[i]].push_back(D[i]);
      g[D[i]].push_back(S[i]);
      subsum[i] = pp[i];
   }
   subsum[N - 1] = pp[N - 1];
   dfs(0);
   solve(0);
   return ans;
}

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