oj.uz

Submission #253349

# Submission time Handle Problem Language Result Execution time Memory
253349 2020-07-27T18:41:10 Z imeimi2000 Traffic (IOI10_traffic) C++17
0 / 100
 14 ms 23808 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Incorrect 14 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Incorrect 14 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Incorrect 14 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Incorrect 14 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -