oj.uz

Submission #296370

# Submission time Handle Problem Language Result Execution time Memory
296370 2020-09-10T13:57:00 Z morato Traffic (IOI10_traffic) C++17
0 / 100
 17 ms 23808 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

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

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

int LocateCentre(int N, int *P, int *S, int *D) {
  for (int i = 0; i < N; i++) {
    p[i] = P[i];
    tot += 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, heavy = h[0];
  for (int i = 1; i < N; i++) {
    h[i] = max(h[i], tot - sub[i] - p[i]);
    if (h[i] < heavy) {
      heavy = h[i];
      ans = i;
    }
  }
  return ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Incorrect 17 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 17 ms 23808 KB Output is correct
2 Incorrect 17 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 17 ms 23808 KB Output is correct
2 Incorrect 17 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 17 ms 23808 KB Output is correct
2 Incorrect 17 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -