# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
336175 |
2020-12-15T00:19:43 Z |
rqi |
Traffic (IOI10_traffic) |
C++14 |
|
17 ms |
23788 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
const ll INF = 1e18;
const int mx = 1000005;
vi adj[mx];
ll sub[mx];
ll sum = 0;
ll ans = INF;
void genSub(int node, int prv = -1){
ll val = 0;
for(auto u: adj[node]){
if(u == prv) continue;
genSub(u, node);
sub[node]+=sub[u];
val = max(val, sub[u]);
}
val = max(val, sum-sub[node]);
ans = min(ans, val);
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for(int i = 0; i < N; i++){
adj[S[i]].pb(D[i]);
adj[D[i]].pb(S[i]);
sub[i]+=P[i];
sum+=P[i];
}
genSub(0);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |