Submission #841686

#	Time	Username	Problem	Language	Result	Execution time	Memory
841686		asdfgrace	Traffic (IOI10_traffic)	C++17	100 / 100	1044 ms	182612 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;

int LocateCentre(int N, int P[], int S[], int D[]) {
  vector<vector<int>> edges(N);
  for (int i = 0; i < N - 1; ++i) {
    edges[S[i]].push_back(D[i]);
    edges[D[i]].push_back(S[i]);
  }
  vector<int> sub(N, 0);
  int tot = 0;
  function<void(int, int)> dfs1 = [&] (int node, int par) {
    for (int next : edges[node]) {
      if (next == par) continue;
      dfs1(next, node);
      sub[node] += sub[next];
    }
    sub[node] += P[node];
    tot += P[node];
  };
  dfs1(0, 0);
  int ans = 0, root = 0;
  for (int ch : edges[0]) {
    ans = max(ans, sub[ch]);
  }
  function<void(int, int)> dfs2 = [&] (int node, int par) -> void {
    int mx = tot - sub[node];
    for (int next : edges[node]) {
      if (next == par) continue;
      mx = max(mx, sub[next]);
    }
    if (mx < ans) {
      ans = mx;
      root = node;
    }
    for (int next : edges[node]) {
      if (next == par) continue;
      dfs2(next, node);
    }
  };
  dfs2(0, 0);
  return root;
}

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