Submission #512480

#	Time	Username	Problem	Language	Result	Execution time	Memory
512480		600Mihnea	Traffic (IOI10_traffic)	C++17	100 / 100	1119 ms	186364 KiB

traffic

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

using namespace std;

int LocateCentre(int n, int cnt[], int S[], int D[]) {
  vector<vector<int>> g(n);
  vector<int> under(n, 0), parrent(n, -1);
  for (int i = 0; i < n - 1; i++) {
    g[S[i]].push_back(D[i]);
    g[D[i]].push_back(S[i]);
  }

  function<void(int, int)> dfs = [&] (int a, int p) {
    parrent[a] = p;
    under[a] = cnt[a];
    for (auto &b : g[a]) {
      if (b != p) {
        dfs(b, a);
        under[a] += under[b];
      }
    }
  };

  dfs(0, -1);
  int mn = (int) 2e9 + 7, best = -1;
  for (int i = 0; i < n; i++) {
    int sol = 0;
    for (auto &j : g[i]) {
      if (j == parrent[i]) {
        sol = max(sol, under[0] - under[i]);
      } else {
        sol = max(sol, under[j]);
      }
    }
    if (sol < mn) {
      best = i;
      mn = sol;
    }
  }
  assert(best != -1);
  return best;
}

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