Submission #253352

#	Time	Username	Problem	Language	Result	Execution time	Memory
253352		imeimi2000	Traffic (IOI10_traffic)	C++17	100 / 100	1283 ms	159224 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

static vector<int> edge[1000000];
static int V[1000000], sz[1000000], par[1000000];

static void dfs(int x, int p) {
  par[x] = p;
  sz[x] = V[x];
  for (int i : edge[x]) {
    if (i == p) continue;
    dfs(i, x);
    sz[x] += sz[i];
  }
}

int LocateCentre(int n, int P[], int S[], int D[]) {
  for (int i = 0; i < n; ++i) {
    edge[i].clear();
    V[i] = P[i];
  }
  for (int i = 0; i < n - 1; ++i) {
    edge[S[i]].push_back(D[i]);
    edge[D[i]].push_back(S[i]);
  }
  dfs(0, -1);
  int ansv = 2e9 + 5, ansi = 0;
  for (int i = 0; i < n; ++i) {
    int mx = 0;
    for (int j : edge[i]) {
      mx = max(mx, par[i] == j ? sz[0] - sz[i] : sz[j]);
    }
    if (mx < ansv) ansv = mx, ansi = i;
  }
  return ansi;
}

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