| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 738625 |
2023-05-09T08:46:57 Z |
Toxtaq |
Traffic (IOI10_traffic) |
C++17 |
|
0 ms |
0 KB |
#include<bits/stdc++.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;
//}
Compilation message
/usr/bin/ld: /tmp/ccHkUPxr.o: in function `main':
grader.cpp:(.text.startup+0xe1): undefined reference to `LocateCentre(int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
