Submission #1183488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183488		peteza	Traffic (IOI10_traffic)	C++20	100 / 100	415 ms	153048 KiB

traffic

#include "traffic.h"
#include <vector>
#include <utility>
#include <climits>
#include <iostream>

std::vector<int> adj[1000005];
long long tot, sz[1000005];
std::pair<long long, int> ans = {LLONG_MAX, -1};

long long dfs(int x, int pp[], int p=-1) {
   sz[x] = pp[x];
   long long cmax = 0;
   for(auto &e:adj[x]) {
      if(e == p) continue;
      cmax = std::max(cmax, dfs(e, pp, x));
      sz[x] += sz[e];
   }
   cmax = std::max(cmax, tot - sz[x]);
   ans = std::min(ans, {cmax, x});
   //std::cout << cmax << ' ' << x << '\n';
   return sz[x];
}

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

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