| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105923 |
2019-04-15T17:44:20 Z |
tincamatei |
Race (IOI11_race) |
C++14 |
|
682 ms |
100428 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000;
vector<pair<int, int> > graph[MAX_N];
set<pair<long long, int> > chains[MAX_N];
long long lazy[MAX_N];
int lazyedge[MAX_N];
int rez = MAX_N + 1;
int subtree[MAX_N];
void predfs(int nod, int papa = -1) {
subtree[nod]++;
for(auto it: graph[nod])
if(it.first != papa) {
predfs(it.first, nod);
subtree[nod] += subtree[it.first];
}
}
void solvedfs(int nod, int k, int papa = -1) {
int heavySon = -1;
for(auto it: graph[nod])
if(it.first != papa && (heavySon == -1 || (heavySon != -1 && subtree[it.first] > subtree[heavySon])))
heavySon = it.first;
for(auto it: graph[nod])
if(it.first != papa) {
solvedfs(it.first, k, nod);
lazy[it.first] += it.second;
lazyedge[it.first]++;
}
if(heavySon != -1) {
// Toarna chestii in heavySon
chains[nod].swap(chains[heavySon]);
swap(lazy[nod], lazy[heavySon]);
swap(lazyedge[nod], lazyedge[heavySon]);
for(auto it: graph[nod])
if(it.first != papa && it.first != heavySon) {
for(auto ch: chains[it.first]) {
set<pair<long long, int> >::iterator lb;
lb = chains[nod].lower_bound(make_pair(k - (ch.first + lazy[it.first]) - lazy[nod], -MAX_N-1));
if(lb != chains[nod].end() && lb->first + ch.first + lazy[it.first] + lazy[nod] == k)
rez = min(rez, ch.second + lb->second + lazyedge[it.first] + lazyedge[nod]);
}
for(auto ch: chains[it.first]) {
chains[nod].insert(make_pair(ch.first + lazy[it.first] - lazy[nod], ch.second + lazyedge[it.first] - lazyedge[nod]));
}
}
}
set<pair<long long, int> >::iterator lb;
lb = chains[nod].lower_bound(make_pair(k - lazy[nod], -MAX_N-1));
if(lb != chains[nod].end() && lb->first + lazy[nod] == k)
rez = min(rez, lb->second + lazyedge[nod]);
chains[nod].insert(make_pair(-lazy[nod], -lazyedge[nod]));
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i < N - 1; ++i)
for(int j = 0; j < 2; ++j)
graph[H[i][j]].push_back(make_pair(H[i][0] ^ H[i][1] ^ H[i][j], L[i]));
predfs(0);
solvedfs(0, K);
if(rez == MAX_N + 1)
return -1;
return rez;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 16 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
14 ms |
14464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 16 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 19 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 20 |
Correct |
14 ms |
14436 KB |
Output is correct |
| 21 |
Correct |
15 ms |
14720 KB |
Output is correct |
| 22 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 23 |
Correct |
16 ms |
14848 KB |
Output is correct |
| 24 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 25 |
Correct |
20 ms |
14720 KB |
Output is correct |
| 26 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 27 |
Correct |
15 ms |
14592 KB |
Output is correct |
| 28 |
Correct |
17 ms |
14720 KB |
Output is correct |
| 29 |
Correct |
17 ms |
14720 KB |
Output is correct |
| 30 |
Correct |
18 ms |
14848 KB |
Output is correct |
| 31 |
Correct |
21 ms |
14720 KB |
Output is correct |
| 32 |
Correct |
23 ms |
14720 KB |
Output is correct |
| 33 |
Correct |
18 ms |
14720 KB |
Output is correct |
| 34 |
Correct |
19 ms |
14636 KB |
Output is correct |
| 35 |
Correct |
21 ms |
14592 KB |
Output is correct |
| 36 |
Correct |
16 ms |
14592 KB |
Output is correct |
| 37 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 38 |
Correct |
16 ms |
14592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 16 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 19 |
Correct |
206 ms |
36772 KB |
Output is correct |
| 20 |
Correct |
240 ms |
37936 KB |
Output is correct |
| 21 |
Correct |
195 ms |
37624 KB |
Output is correct |
| 22 |
Correct |
202 ms |
36860 KB |
Output is correct |
| 23 |
Correct |
306 ms |
52332 KB |
Output is correct |
| 24 |
Correct |
190 ms |
40780 KB |
Output is correct |
| 25 |
Correct |
214 ms |
40824 KB |
Output is correct |
| 26 |
Correct |
126 ms |
46756 KB |
Output is correct |
| 27 |
Correct |
315 ms |
46464 KB |
Output is correct |
| 28 |
Correct |
369 ms |
79392 KB |
Output is correct |
| 29 |
Correct |
393 ms |
77520 KB |
Output is correct |
| 30 |
Correct |
354 ms |
46456 KB |
Output is correct |
| 31 |
Correct |
331 ms |
46340 KB |
Output is correct |
| 32 |
Correct |
422 ms |
46452 KB |
Output is correct |
| 33 |
Correct |
354 ms |
42204 KB |
Output is correct |
| 34 |
Correct |
492 ms |
75040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 6 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 7 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 8 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 10 |
Correct |
17 ms |
14464 KB |
Output is correct |
| 11 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 12 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 13 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 14 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 16 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 17 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 18 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 19 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 20 |
Correct |
14 ms |
14436 KB |
Output is correct |
| 21 |
Correct |
15 ms |
14720 KB |
Output is correct |
| 22 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 23 |
Correct |
16 ms |
14848 KB |
Output is correct |
| 24 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 25 |
Correct |
20 ms |
14720 KB |
Output is correct |
| 26 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 27 |
Correct |
15 ms |
14592 KB |
Output is correct |
| 28 |
Correct |
17 ms |
14720 KB |
Output is correct |
| 29 |
Correct |
17 ms |
14720 KB |
Output is correct |
| 30 |
Correct |
18 ms |
14848 KB |
Output is correct |
| 31 |
Correct |
21 ms |
14720 KB |
Output is correct |
| 32 |
Correct |
23 ms |
14720 KB |
Output is correct |
| 33 |
Correct |
18 ms |
14720 KB |
Output is correct |
| 34 |
Correct |
19 ms |
14636 KB |
Output is correct |
| 35 |
Correct |
21 ms |
14592 KB |
Output is correct |
| 36 |
Correct |
16 ms |
14592 KB |
Output is correct |
| 37 |
Correct |
16 ms |
14720 KB |
Output is correct |
| 38 |
Correct |
16 ms |
14592 KB |
Output is correct |
| 39 |
Correct |
206 ms |
36772 KB |
Output is correct |
| 40 |
Correct |
240 ms |
37936 KB |
Output is correct |
| 41 |
Correct |
195 ms |
37624 KB |
Output is correct |
| 42 |
Correct |
202 ms |
36860 KB |
Output is correct |
| 43 |
Correct |
306 ms |
52332 KB |
Output is correct |
| 44 |
Correct |
190 ms |
40780 KB |
Output is correct |
| 45 |
Correct |
214 ms |
40824 KB |
Output is correct |
| 46 |
Correct |
126 ms |
46756 KB |
Output is correct |
| 47 |
Correct |
315 ms |
46464 KB |
Output is correct |
| 48 |
Correct |
369 ms |
79392 KB |
Output is correct |
| 49 |
Correct |
393 ms |
77520 KB |
Output is correct |
| 50 |
Correct |
354 ms |
46456 KB |
Output is correct |
| 51 |
Correct |
331 ms |
46340 KB |
Output is correct |
| 52 |
Correct |
422 ms |
46452 KB |
Output is correct |
| 53 |
Correct |
354 ms |
42204 KB |
Output is correct |
| 54 |
Correct |
492 ms |
75040 KB |
Output is correct |
| 55 |
Correct |
32 ms |
17532 KB |
Output is correct |
| 56 |
Correct |
27 ms |
16376 KB |
Output is correct |
| 57 |
Correct |
116 ms |
34680 KB |
Output is correct |
| 58 |
Correct |
67 ms |
28396 KB |
Output is correct |
| 59 |
Correct |
105 ms |
46712 KB |
Output is correct |
| 60 |
Correct |
426 ms |
78040 KB |
Output is correct |
| 61 |
Correct |
370 ms |
52188 KB |
Output is correct |
| 62 |
Correct |
317 ms |
46480 KB |
Output is correct |
| 63 |
Correct |
445 ms |
46668 KB |
Output is correct |
| 64 |
Correct |
627 ms |
100428 KB |
Output is correct |
| 65 |
Correct |
597 ms |
94776 KB |
Output is correct |
| 66 |
Correct |
410 ms |
73464 KB |
Output is correct |
| 67 |
Correct |
342 ms |
43876 KB |
Output is correct |
| 68 |
Correct |
682 ms |
63608 KB |
Output is correct |
| 69 |
Correct |
615 ms |
64376 KB |
Output is correct |
| 70 |
Correct |
550 ms |
61720 KB |
Output is correct |
