# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
764267 |
2023-06-23T09:48:12 Z |
Blagoj |
Traffic (IOI10_traffic) |
C++17 |
|
13 ms |
23764 KB |
#include <bits/stdc++.h>
#include "traffic.h"
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
vector<int> g[1000003];
int sz[1000003], ppl[1000003];
bool visited[1000003];
void dfs(int n, int p = -1) {
sz[n] = ppl[n];
for (auto x : g[n]) {
if (x == p) continue;
dfs(x, n);
sz[n] += sz[x];
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N - 1; i++) g[S[i]].push_back(D[i]);
for (int i = 0; i < N; i++) ppl[i] = pp[i];
dfs(0);
queue<pair<int, int>> q;
q.push({0, 0});
visited[0] = 1;
ll best = LLONG_MAX, id = 0;
while (q.size() > 0) {
int place = q.front().first, sum = q.front().second, cnt = 0, mx = sum;
q.pop();
for (auto x : g[place]) {
if (visited[x]) continue;
mx = max(mx, sz[x]);
cnt += sz[x];
}
if (mx < best) {
best = mx;
id = place;
}
for (auto x : g[place]) {
if (visited[x]) continue;
visited[x] = 1;
q.push({x, sz[place] + sum + cnt - sz[x]});
}
}
return id;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |