# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1198492 | AMel0n | Traffic (IOI10_traffic) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first
// #define S second
#include "traffic.h"
int N;
vector<int> P, S, D;
int tot, mn = INT_MAX;
vector<vector<int>> adj;
int dfs(int n, int p) {
int ss = 0;
for(auto c: adj[n]) {
if (c != p) ss += dfs(c, n);
}
mn = min(mn, ss + (tot - ss - P[n]));
return ss + P[n];
}
int LocateCentre(int N, vector<int> P, vector<int> S, vector<int> D) {
::N = N;
::P = P;
::S = S;
::D = D;
tot = accumulate(all(P), 0);
adj.resize(N);
FOR(i, N-1) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0,0);
return mn;
}
// signed main() {
// cin.tie(0); ios::sync_with_stdio(false);
// }