| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 866689 |
2023-10-26T18:03:11 Z |
Irate |
Race (IOI11_race) |
C++14 |
|
372 ms |
107444 KB |
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int mxN = 2e5 + 3;
vector<pair<int, int>>G[mxN];
map<long long, int>cnt[mxN];
long long length[mxN];
int K, mn = 1e9, depth[mxN];
void dfs(int node, int par){
cnt[node][length[node]] = depth[node];
for(pair<int, int>& v : G[node]){
if(v.first != par){
depth[v.first] = depth[node] + 1;
length[v.first] = length[node] + v.second;
dfs(v.first, node);
if(cnt[node].size() < cnt[v.first].size())swap(cnt[node], cnt[v.first]);
for(auto itr = cnt[v.first].begin();itr != cnt[v.first].end();++itr){
long long num = itr->first;
int dep = itr->second;
if(cnt[node].count(K + 2 * length[node] - num)){
mn = min(mn, dep + cnt[node][K + 2 * length[node] - num] - 2 * depth[node]);
}
}
for(auto itr = cnt[v.first].begin();itr != cnt[v.first].end();++itr){
if(cnt[node].count(itr->first)){
cnt[node][itr->first] = min(cnt[node][itr->first], itr->second);
}
else{
cnt[node][itr->first] = itr->second;
}
}
}
}
}
int best_path(int n, int k, int H[][2], int L[]){
K = k;
for(int i = 0;i < n - 1;++i){
int u = H[i][0], v = H[i][1];
G[u].push_back({v, L[i]});
G[v].push_back({u, L[i]});
}
dfs(0, 0);
if(mn == 1e9)return -1;
return mn;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int n;
// cin >> n >> K;
// int H[n - 1][2], L[n - 1];
// for(int i = 0;i < n - 1;++i){
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// cout << best_path(n, K, H, L);
// }
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
20312 KB |
Output is correct |
| 2 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 4 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 5 |
Correct |
5 ms |
20568 KB |
Output is correct |
| 6 |
Correct |
4 ms |
20516 KB |
Output is correct |
| 7 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 8 |
Correct |
4 ms |
20380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 10 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 11 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 12 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 13 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 14 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 15 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 16 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 17 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 18 |
Correct |
5 ms |
20316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
20312 KB |
Output is correct |
| 2 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 4 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 5 |
Correct |
5 ms |
20568 KB |
Output is correct |
| 6 |
Correct |
4 ms |
20516 KB |
Output is correct |
| 7 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 8 |
Correct |
4 ms |
20380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 10 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 11 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 12 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 13 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 14 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 15 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 16 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 17 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 18 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 19 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 20 |
Correct |
4 ms |
20488 KB |
Output is correct |
| 21 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 22 |
Correct |
5 ms |
20824 KB |
Output is correct |
| 23 |
Correct |
5 ms |
20584 KB |
Output is correct |
| 24 |
Correct |
5 ms |
20784 KB |
Output is correct |
| 25 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 26 |
Correct |
6 ms |
20828 KB |
Output is correct |
| 27 |
Correct |
4 ms |
20568 KB |
Output is correct |
| 28 |
Correct |
6 ms |
20572 KB |
Output is correct |
| 29 |
Correct |
6 ms |
20784 KB |
Output is correct |
| 30 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 31 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 32 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 33 |
Correct |
5 ms |
20828 KB |
Output is correct |
| 34 |
Correct |
4 ms |
20572 KB |
Output is correct |
| 35 |
Correct |
4 ms |
20572 KB |
Output is correct |
| 36 |
Correct |
4 ms |
20544 KB |
Output is correct |
| 37 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 38 |
Correct |
5 ms |
20572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
20312 KB |
Output is correct |
| 2 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 4 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 5 |
Correct |
5 ms |
20568 KB |
Output is correct |
| 6 |
Correct |
4 ms |
20516 KB |
Output is correct |
| 7 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 8 |
Correct |
4 ms |
20380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 10 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 11 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 12 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 13 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 14 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 15 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 16 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 17 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 18 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 19 |
Correct |
91 ms |
43032 KB |
Output is correct |
| 20 |
Correct |
91 ms |
43092 KB |
Output is correct |
| 21 |
Correct |
86 ms |
42672 KB |
Output is correct |
| 22 |
Correct |
108 ms |
42308 KB |
Output is correct |
| 23 |
Correct |
131 ms |
55124 KB |
Output is correct |
| 24 |
Correct |
102 ms |
45648 KB |
Output is correct |
| 25 |
Correct |
79 ms |
41296 KB |
Output is correct |
| 26 |
Correct |
48 ms |
47188 KB |
Output is correct |
| 27 |
Correct |
142 ms |
50936 KB |
Output is correct |
| 28 |
Correct |
257 ms |
84084 KB |
Output is correct |
| 29 |
Correct |
246 ms |
83028 KB |
Output is correct |
| 30 |
Correct |
143 ms |
50932 KB |
Output is correct |
| 31 |
Correct |
148 ms |
51152 KB |
Output is correct |
| 32 |
Correct |
191 ms |
51048 KB |
Output is correct |
| 33 |
Correct |
180 ms |
55844 KB |
Output is correct |
| 34 |
Correct |
274 ms |
88824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
20312 KB |
Output is correct |
| 2 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 4 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 5 |
Correct |
5 ms |
20568 KB |
Output is correct |
| 6 |
Correct |
4 ms |
20516 KB |
Output is correct |
| 7 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 8 |
Correct |
4 ms |
20380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 10 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 11 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 12 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 13 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 14 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 15 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 16 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 17 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 18 |
Correct |
5 ms |
20316 KB |
Output is correct |
| 19 |
Correct |
4 ms |
20316 KB |
Output is correct |
| 20 |
Correct |
4 ms |
20488 KB |
Output is correct |
| 21 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 22 |
Correct |
5 ms |
20824 KB |
Output is correct |
| 23 |
Correct |
5 ms |
20584 KB |
Output is correct |
| 24 |
Correct |
5 ms |
20784 KB |
Output is correct |
| 25 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 26 |
Correct |
6 ms |
20828 KB |
Output is correct |
| 27 |
Correct |
4 ms |
20568 KB |
Output is correct |
| 28 |
Correct |
6 ms |
20572 KB |
Output is correct |
| 29 |
Correct |
6 ms |
20784 KB |
Output is correct |
| 30 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 31 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 32 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 33 |
Correct |
5 ms |
20828 KB |
Output is correct |
| 34 |
Correct |
4 ms |
20572 KB |
Output is correct |
| 35 |
Correct |
4 ms |
20572 KB |
Output is correct |
| 36 |
Correct |
4 ms |
20544 KB |
Output is correct |
| 37 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 38 |
Correct |
5 ms |
20572 KB |
Output is correct |
| 39 |
Correct |
91 ms |
43032 KB |
Output is correct |
| 40 |
Correct |
91 ms |
43092 KB |
Output is correct |
| 41 |
Correct |
86 ms |
42672 KB |
Output is correct |
| 42 |
Correct |
108 ms |
42308 KB |
Output is correct |
| 43 |
Correct |
131 ms |
55124 KB |
Output is correct |
| 44 |
Correct |
102 ms |
45648 KB |
Output is correct |
| 45 |
Correct |
79 ms |
41296 KB |
Output is correct |
| 46 |
Correct |
48 ms |
47188 KB |
Output is correct |
| 47 |
Correct |
142 ms |
50936 KB |
Output is correct |
| 48 |
Correct |
257 ms |
84084 KB |
Output is correct |
| 49 |
Correct |
246 ms |
83028 KB |
Output is correct |
| 50 |
Correct |
143 ms |
50932 KB |
Output is correct |
| 51 |
Correct |
148 ms |
51152 KB |
Output is correct |
| 52 |
Correct |
191 ms |
51048 KB |
Output is correct |
| 53 |
Correct |
180 ms |
55844 KB |
Output is correct |
| 54 |
Correct |
274 ms |
88824 KB |
Output is correct |
| 55 |
Correct |
15 ms |
23388 KB |
Output is correct |
| 56 |
Correct |
10 ms |
22108 KB |
Output is correct |
| 57 |
Correct |
59 ms |
40276 KB |
Output is correct |
| 58 |
Correct |
41 ms |
33732 KB |
Output is correct |
| 59 |
Correct |
86 ms |
53696 KB |
Output is correct |
| 60 |
Correct |
250 ms |
84252 KB |
Output is correct |
| 61 |
Correct |
176 ms |
55764 KB |
Output is correct |
| 62 |
Correct |
139 ms |
52272 KB |
Output is correct |
| 63 |
Correct |
189 ms |
52308 KB |
Output is correct |
| 64 |
Correct |
372 ms |
107444 KB |
Output is correct |
| 65 |
Correct |
369 ms |
105640 KB |
Output is correct |
| 66 |
Correct |
271 ms |
81452 KB |
Output is correct |
| 67 |
Correct |
136 ms |
46784 KB |
Output is correct |
| 68 |
Correct |
289 ms |
69392 KB |
Output is correct |
| 69 |
Correct |
308 ms |
74248 KB |
Output is correct |
| 70 |
Correct |
276 ms |
67596 KB |
Output is correct |
