| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684052 |
2023-01-20T08:18:43 Z |
fuad27 |
Race (IOI11_race) |
C++17 |
|
1240 ms |
51660 KB |
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N =200'010;
long long K=0;
vector<pair<int, long long>> g[N];
vector<bool> R(N);
int dp[N];
int dfs(int at, int p) {
dp[at]=1;
for(auto to:g[at]) {
if(to.first!=p and !R[to.first]) {
dp[at]+=dfs(to.first,at);
}
}
return dp[at];
}
int get_centroid(int at, int sz, int p) {
for(auto to:g[at]) {
if(to.first==p or R[to.first])continue;
if(dp[to.first]*2>sz)return get_centroid(to.first,sz,at);
}
return at;
}
long long res=1e18;
map<long long, int> mp;
map<long long, int> mp2;
void dfs1(int at, int p, long long w, int d=1) {
if(mp2.find(w)==mp2.end() or mp2[w]>d) {
mp2[w]=d;
if(mp.find(K-w)!=mp.end())
res=min(res,(long long)mp2[w]+mp[K-w]);
}
for(auto to:g[at]) {
if(R[to.first])continue;
if(to.first==p)continue;
dfs1(to.first,at,w+to.second,d+1);
}
}
void get(int at) {
mp.clear();
mp2.clear();
mp[0]=0;
for(auto to:g[at]) {
if(R[to.first])continue;
dfs1(to.first,at,to.second);
for(auto i:mp2) {
if(mp.find(i.first)==mp.end())mp[i.first]=i.second;
else mp[i.first]=min(mp[i.first],i.second);
}
mp2.clear();
}
}
void centroid(int n=0) {
int C=get_centroid(n,dfs(n,-1),-1);
get(C);
R[C]=1;
for(auto to:g[C]) {
if(!R[to.first])centroid(to.first);
}
}
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]].push_back({h[i][1],l[i]});
g[h[i][1]].push_back({h[i][0],l[i]});
}
centroid();
if(res==1e18)return -1;
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5152 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5176 KB |
Output is correct |
| 23 |
Correct |
6 ms |
5212 KB |
Output is correct |
| 24 |
Correct |
5 ms |
5172 KB |
Output is correct |
| 25 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 26 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5044 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 29 |
Correct |
4 ms |
5176 KB |
Output is correct |
| 30 |
Correct |
6 ms |
5176 KB |
Output is correct |
| 31 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 32 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 33 |
Correct |
5 ms |
5180 KB |
Output is correct |
| 34 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 35 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 36 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 37 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 38 |
Correct |
5 ms |
5076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
260 ms |
13060 KB |
Output is correct |
| 20 |
Correct |
243 ms |
13068 KB |
Output is correct |
| 21 |
Correct |
227 ms |
12972 KB |
Output is correct |
| 22 |
Correct |
213 ms |
13100 KB |
Output is correct |
| 23 |
Correct |
329 ms |
13620 KB |
Output is correct |
| 24 |
Correct |
165 ms |
12748 KB |
Output is correct |
| 25 |
Correct |
170 ms |
18736 KB |
Output is correct |
| 26 |
Correct |
91 ms |
18856 KB |
Output is correct |
| 27 |
Correct |
369 ms |
22060 KB |
Output is correct |
| 28 |
Correct |
1240 ms |
51660 KB |
Output is correct |
| 29 |
Correct |
1228 ms |
50852 KB |
Output is correct |
| 30 |
Correct |
377 ms |
21972 KB |
Output is correct |
| 31 |
Correct |
352 ms |
22056 KB |
Output is correct |
| 32 |
Correct |
436 ms |
22132 KB |
Output is correct |
| 33 |
Correct |
522 ms |
21004 KB |
Output is correct |
| 34 |
Correct |
1054 ms |
37264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 16 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5152 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5176 KB |
Output is correct |
| 23 |
Correct |
6 ms |
5212 KB |
Output is correct |
| 24 |
Correct |
5 ms |
5172 KB |
Output is correct |
| 25 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 26 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5044 KB |
Output is correct |
| 28 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 29 |
Correct |
4 ms |
5176 KB |
Output is correct |
| 30 |
Correct |
6 ms |
5176 KB |
Output is correct |
| 31 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 32 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 33 |
Correct |
5 ms |
5180 KB |
Output is correct |
| 34 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 35 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 36 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 37 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 38 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 39 |
Correct |
260 ms |
13060 KB |
Output is correct |
| 40 |
Correct |
243 ms |
13068 KB |
Output is correct |
| 41 |
Correct |
227 ms |
12972 KB |
Output is correct |
| 42 |
Correct |
213 ms |
13100 KB |
Output is correct |
| 43 |
Correct |
329 ms |
13620 KB |
Output is correct |
| 44 |
Correct |
165 ms |
12748 KB |
Output is correct |
| 45 |
Correct |
170 ms |
18736 KB |
Output is correct |
| 46 |
Correct |
91 ms |
18856 KB |
Output is correct |
| 47 |
Correct |
369 ms |
22060 KB |
Output is correct |
| 48 |
Correct |
1240 ms |
51660 KB |
Output is correct |
| 49 |
Correct |
1228 ms |
50852 KB |
Output is correct |
| 50 |
Correct |
377 ms |
21972 KB |
Output is correct |
| 51 |
Correct |
352 ms |
22056 KB |
Output is correct |
| 52 |
Correct |
436 ms |
22132 KB |
Output is correct |
| 53 |
Correct |
522 ms |
21004 KB |
Output is correct |
| 54 |
Correct |
1054 ms |
37264 KB |
Output is correct |
| 55 |
Correct |
28 ms |
6228 KB |
Output is correct |
| 56 |
Correct |
17 ms |
5776 KB |
Output is correct |
| 57 |
Correct |
156 ms |
13408 KB |
Output is correct |
| 58 |
Correct |
53 ms |
12356 KB |
Output is correct |
| 59 |
Correct |
431 ms |
26708 KB |
Output is correct |
| 60 |
Correct |
1217 ms |
50096 KB |
Output is correct |
| 61 |
Correct |
410 ms |
23892 KB |
Output is correct |
| 62 |
Correct |
384 ms |
22224 KB |
Output is correct |
| 63 |
Correct |
409 ms |
22124 KB |
Output is correct |
| 64 |
Correct |
1227 ms |
30628 KB |
Output is correct |
| 65 |
Correct |
1026 ms |
35264 KB |
Output is correct |
| 66 |
Correct |
1238 ms |
50476 KB |
Output is correct |
| 67 |
Correct |
141 ms |
21080 KB |
Output is correct |
| 68 |
Correct |
586 ms |
32568 KB |
Output is correct |
| 69 |
Correct |
611 ms |
32892 KB |
Output is correct |
| 70 |
Correct |
559 ms |
31276 KB |
Output is correct |
