# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
98936 |
2019-02-27T15:25:11 Z |
Hideo |
Race (IOI11_race) |
C++14 |
|
32 ms |
17792 KB |
#include "race.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define mk make_pair
#define pb push_back
#define sc second
#define fr first
#define pii pair < int, int >
#define vii vector < pii >
const int MAXN = 2e5 + 7;
const int MAXK = 1e6 + 7;
const int INF = 1e9 + 7;
int ans = INF, k;
int st[MAXK], h[MAXN], del[MAXN];
vii g[MAXN];
void dfs (int v, int p = -1){
h[v] = 1;
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
dfs(to.fr, v);
if (p != -1)
h[p] += h[v];
}
int centroid (int v){
dfs(v);
bool ok = false;
int c = v, pr = 0;
while (ok){
ok = false;
for (pii to : g[c]){
if (to.fr != pr && !del[to.fr] && h[to.fr] * 2 >= h[v]){
pr = c;
c = to.fr;
ok = true;
break;
}
}
}
return c;
}
void findAns (int v, int p, int l, int d = 1){
if (k > l && st[k - l])
ans = min(ans, d + st[k - l]);
if (k == l)
ans = min(ans, d);
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
findAns (to.fr, v, l + to.sc, d + 1);
}
void upd (int v, int p, int l, int d = 1){
if (st[l] && k >= l)
st[l] = min(st[l], d);
else if (k >= l)
st[l] = d;
for (pii to : g[v])
if (to.fr != p && !del[to.fr])
upd(to.fr, v, l + to.sc, d + 1);
}
void calc (int v = 0){
v = centroid(v);
del[v] = 1;
memset(st, 0, sizeof(st));
for (pii to : g[v]){
if (!del[to.fr]){
findAns(to.fr, v, to.sc);
upd(to.fr, v, to.sc);
}
}
for (pii to : g[v])
if (!del[to.fr])
calc (to.fr);
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; i++){
g[H[i][0]].pb(mk(H[i][1], L[i]));
g[H[i][1]].pb(mk(H[i][0], L[i]));
}
calc();
if (ans == INF)
return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8960 KB |
Output is correct |
2 |
Correct |
29 ms |
8960 KB |
Output is correct |
3 |
Correct |
30 ms |
8960 KB |
Output is correct |
4 |
Correct |
32 ms |
8960 KB |
Output is correct |
5 |
Runtime error |
23 ms |
17792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8960 KB |
Output is correct |
2 |
Correct |
29 ms |
8960 KB |
Output is correct |
3 |
Correct |
30 ms |
8960 KB |
Output is correct |
4 |
Correct |
32 ms |
8960 KB |
Output is correct |
5 |
Runtime error |
23 ms |
17792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8960 KB |
Output is correct |
2 |
Correct |
29 ms |
8960 KB |
Output is correct |
3 |
Correct |
30 ms |
8960 KB |
Output is correct |
4 |
Correct |
32 ms |
8960 KB |
Output is correct |
5 |
Runtime error |
23 ms |
17792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8960 KB |
Output is correct |
2 |
Correct |
29 ms |
8960 KB |
Output is correct |
3 |
Correct |
30 ms |
8960 KB |
Output is correct |
4 |
Correct |
32 ms |
8960 KB |
Output is correct |
5 |
Runtime error |
23 ms |
17792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |