Submission #253349

#	Time	Username	Problem	Language	Result	Execution time	Memory
253349		imeimi2000	Traffic (IOI10_traffic)	C++17	0 / 100	14 ms	23808 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 ans = 2e9 + 5;
  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]);
    }
    ans = min(ans, mx);
  }
  return ans;
}

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