Submission #1080031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080031		juicy	Traffic (IOI10_traffic)	C++17	100 / 100	622 ms	213748 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>

using namespace std;

int LocateCentre(int n, int *a, int *s, int *d) {
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    g[s[i]].push_back(d[i]);
    g[d[i]].push_back(s[i]);
  }
  array<int, 2> res = {INT_MAX, -1};
  vector<int> sz(n);
  int tot = accumulate(a, a + n, 0);
  function<void(int)> dfs = [&](int u) {
    sz[u] = a[u];
    int ma = 0;
    for (int v : g[u]) {
      if (!sz[v]) {
        dfs(v);
        ma = max(ma, sz[v]);
        sz[u] += sz[v];
      }
    }
    ma = max(ma, tot - sz[u]);
    res = min(res, {ma, u});
  };
  dfs(0);
  return res[1];
}

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