Submission #296416

#	Time	Username	Problem	Language	Result	Execution time	Memory
296416		morato	Traffic (IOI10_traffic)	C++17	0 / 100	17 ms	23900 KiB

traffic

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

const int maxn = 1e6 + 5;

vector<int> adj[maxn];
int64_t p[maxn], h[maxn], sub[maxn], tot;

int64_t dfs(int v, int _p = -1) {
  sub[v] = p[v];
  for (int u : adj[v]) if (u != _p) {
    int64_t wgt = dfs(u, v);
    sub[v] += wgt;
    h[v] = max(h[v], wgt);
  }
  return sub[v];
}

int LocateCentre(int N, int P[], int S[], int D[]) {
  for (int i = 0; i < N; i++) {
    p[i] = P[i];
  }
  for (int i = 0; i < N; i++) {
    adj[S[i]].push_back(D[i]);
    adj[D[i]].push_back(S[i]);
  }
  dfs(0);
  int ans = 0;
  int64_t heavy = sub[0] - p[0];
  for (int i = 1; i < N; i++) {
    h[i] = max(h[i], sub[0] - sub[i]);
    if (h[i] < heavy) {
      heavy = h[i];
      ans = i;
    }
  }
  return ans;
}

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