| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 738626 | Toxtaq | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;
vector<vector<int>>g;
vector<int>fans;
vector<int>sub, res;
void calc(int node, int par){
sub[node] = fans[node];
for(int v : g[node]){
if(v != par){
calc(v, node);
sub[node] += sub[v];
}
}
}
void traverse(int node, int par){
res[node] = max(res[node], sub[par] - sub[node]);
for(int v : g[node]){
if(v == par)continue;
res[node] = max(sub[v], res[node]);
}
for(int v : g[node]){
if(v != par){
traverse(v, node);
}
}
}
int LocateCentre(int n, vector<int>p, vector<int>s, vector<int>d){
g.resize(n);
fans.resize(n);
res.resize(n);
sub.resize(n);
for(int i = 0;i < n - 1;++i){
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
for(int i = 0;i < n;++i){
fans[i] = p[i];
}
calc(1, 1);
traverse(1, 1);
int mn = 1e9, id = -1;
for(int i = 0;i < n;++i){
if(mn > res[i]){
mn = res[i];
id = i;
}
}
return id;
}
//int main()
//{
// int n;
// cin >> n;
// g.resize(n);
// fans.resize(n);
// res.resize(n);
// sub.resize(n);
// for(int i = 0;i < n - 1;++i){
// int u, v;
// cin >> u >> v;
// g[u].push_back(v);
// g[v].push_back(u);
// }
// for(int i = 0;i < n;++i){
// cin >> fans[i];
// }
// calc(1, 1);
// traverse(1, 1);
// int mn = 1e9, id = -1;
// for(int i = 0;i < n;++i){
// if(mn > res[i]){
// mn = res[i];
// id = i;
// }
// }
// cout << id;
//}