# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
964934 |
2024-04-17T18:05:47 Z |
Younis_Dwai |
Race (IOI11_race) |
C++14 |
|
3000 ms |
41544 KB |
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std ;
const int MN=1e6+1;
bitset<MN> vis;
int res,k;
vector<int> dp(MN),sz(MN);
vector<pair<int,int>> adj[MN];
void dfs_sz(int node , int par){
sz[node]=1;
for(auto u : adj[node]){
if(vis[u.F] || u.F==par) continue ;
dfs_sz(u.F,node);
}
return ;
}
int get_centroid(int node ,int par , int d){
for(auto u : adj[node]){
if(vis[u.F] || u.F==par || sz[u.F]<=d) continue ;
return get_centroid(u.F,node,d);
}
return node;
}
void dfs_calc(int node, int par , int done ,int dis){
res=min(res,dp[k-dis]+done);
for(auto u : adj[node]){
if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
dfs_calc(u.F,node,done+1,dis+u.S);
}
return ;
}
void dfs_upd(int node , int par , int done , int dis){
dp[dis]=min(done,dp[dis]);
for(auto u : adj[node]){
if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
dfs_upd(u.F,node,done+1,dis+u.S);
}
return ;
}
void dfs_fill(int node , int par ,int dis){
dp[dis]=1e9;
for(auto u : adj[node]){
if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
dfs_fill(u.F,node,dis+u.S);
}
return ;
}
void dfs(int node){
dfs_sz(node,node);
int centroid=get_centroid(node,node,sz[node]/2);
vis[centroid]=1;
dp[0]=0;
for(auto u : adj[centroid]){
if(vis[u.F] || u.S>k) continue ;
dfs_calc(u.F,centroid,1,u.S);
dfs_upd(u.F,centroid,1,u.S);
}
for(auto u : adj[centroid]){
if(u.S>k || vis[u.F]) continue ;
dfs_fill(u.F,centroid,u.S);
}
for(auto u : adj[centroid]){
if(vis[u.F]) continue ;
dfs(u.F);
}
return ;
}
int best_path(int N, int K, int H[][2], int L[]){
res=1e9;
k=K;
for(int i=0;i<=K;i++) dp[i]=1e9;
for(int i=0;i<N-1;i++){
adj[H[i][0]].pb({H[i][1],L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
dfs(0);
if(res==1e9) return -1;
else return res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35164 KB |
Output is correct |
3 |
Correct |
10 ms |
35160 KB |
Output is correct |
4 |
Correct |
10 ms |
35164 KB |
Output is correct |
5 |
Correct |
9 ms |
35268 KB |
Output is correct |
6 |
Correct |
10 ms |
35164 KB |
Output is correct |
7 |
Correct |
10 ms |
35164 KB |
Output is correct |
8 |
Correct |
12 ms |
35164 KB |
Output is correct |
9 |
Correct |
10 ms |
35416 KB |
Output is correct |
10 |
Correct |
10 ms |
35164 KB |
Output is correct |
11 |
Correct |
9 ms |
35168 KB |
Output is correct |
12 |
Correct |
9 ms |
35164 KB |
Output is correct |
13 |
Correct |
12 ms |
35348 KB |
Output is correct |
14 |
Correct |
10 ms |
35164 KB |
Output is correct |
15 |
Correct |
10 ms |
35420 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
12 ms |
35164 KB |
Output is correct |
18 |
Correct |
10 ms |
35172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35164 KB |
Output is correct |
3 |
Correct |
10 ms |
35160 KB |
Output is correct |
4 |
Correct |
10 ms |
35164 KB |
Output is correct |
5 |
Correct |
9 ms |
35268 KB |
Output is correct |
6 |
Correct |
10 ms |
35164 KB |
Output is correct |
7 |
Correct |
10 ms |
35164 KB |
Output is correct |
8 |
Correct |
12 ms |
35164 KB |
Output is correct |
9 |
Correct |
10 ms |
35416 KB |
Output is correct |
10 |
Correct |
10 ms |
35164 KB |
Output is correct |
11 |
Correct |
9 ms |
35168 KB |
Output is correct |
12 |
Correct |
9 ms |
35164 KB |
Output is correct |
13 |
Correct |
12 ms |
35348 KB |
Output is correct |
14 |
Correct |
10 ms |
35164 KB |
Output is correct |
15 |
Correct |
10 ms |
35420 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
12 ms |
35164 KB |
Output is correct |
18 |
Correct |
10 ms |
35172 KB |
Output is correct |
19 |
Correct |
9 ms |
35164 KB |
Output is correct |
20 |
Correct |
9 ms |
35164 KB |
Output is correct |
21 |
Correct |
26 ms |
35460 KB |
Output is correct |
22 |
Correct |
14 ms |
35420 KB |
Output is correct |
23 |
Correct |
14 ms |
35416 KB |
Output is correct |
24 |
Correct |
14 ms |
35416 KB |
Output is correct |
25 |
Correct |
37 ms |
35444 KB |
Output is correct |
26 |
Correct |
14 ms |
35420 KB |
Output is correct |
27 |
Correct |
14 ms |
35420 KB |
Output is correct |
28 |
Correct |
17 ms |
35420 KB |
Output is correct |
29 |
Correct |
23 ms |
35440 KB |
Output is correct |
30 |
Correct |
23 ms |
35420 KB |
Output is correct |
31 |
Correct |
26 ms |
35480 KB |
Output is correct |
32 |
Correct |
29 ms |
35464 KB |
Output is correct |
33 |
Correct |
28 ms |
35420 KB |
Output is correct |
34 |
Correct |
15 ms |
35464 KB |
Output is correct |
35 |
Correct |
15 ms |
35472 KB |
Output is correct |
36 |
Correct |
18 ms |
35420 KB |
Output is correct |
37 |
Correct |
22 ms |
35420 KB |
Output is correct |
38 |
Correct |
26 ms |
35460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35164 KB |
Output is correct |
3 |
Correct |
10 ms |
35160 KB |
Output is correct |
4 |
Correct |
10 ms |
35164 KB |
Output is correct |
5 |
Correct |
9 ms |
35268 KB |
Output is correct |
6 |
Correct |
10 ms |
35164 KB |
Output is correct |
7 |
Correct |
10 ms |
35164 KB |
Output is correct |
8 |
Correct |
12 ms |
35164 KB |
Output is correct |
9 |
Correct |
10 ms |
35416 KB |
Output is correct |
10 |
Correct |
10 ms |
35164 KB |
Output is correct |
11 |
Correct |
9 ms |
35168 KB |
Output is correct |
12 |
Correct |
9 ms |
35164 KB |
Output is correct |
13 |
Correct |
12 ms |
35348 KB |
Output is correct |
14 |
Correct |
10 ms |
35164 KB |
Output is correct |
15 |
Correct |
10 ms |
35420 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
12 ms |
35164 KB |
Output is correct |
18 |
Correct |
10 ms |
35172 KB |
Output is correct |
19 |
Execution timed out |
3007 ms |
41544 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
35160 KB |
Output is correct |
2 |
Correct |
9 ms |
35164 KB |
Output is correct |
3 |
Correct |
10 ms |
35160 KB |
Output is correct |
4 |
Correct |
10 ms |
35164 KB |
Output is correct |
5 |
Correct |
9 ms |
35268 KB |
Output is correct |
6 |
Correct |
10 ms |
35164 KB |
Output is correct |
7 |
Correct |
10 ms |
35164 KB |
Output is correct |
8 |
Correct |
12 ms |
35164 KB |
Output is correct |
9 |
Correct |
10 ms |
35416 KB |
Output is correct |
10 |
Correct |
10 ms |
35164 KB |
Output is correct |
11 |
Correct |
9 ms |
35168 KB |
Output is correct |
12 |
Correct |
9 ms |
35164 KB |
Output is correct |
13 |
Correct |
12 ms |
35348 KB |
Output is correct |
14 |
Correct |
10 ms |
35164 KB |
Output is correct |
15 |
Correct |
10 ms |
35420 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
12 ms |
35164 KB |
Output is correct |
18 |
Correct |
10 ms |
35172 KB |
Output is correct |
19 |
Correct |
9 ms |
35164 KB |
Output is correct |
20 |
Correct |
9 ms |
35164 KB |
Output is correct |
21 |
Correct |
26 ms |
35460 KB |
Output is correct |
22 |
Correct |
14 ms |
35420 KB |
Output is correct |
23 |
Correct |
14 ms |
35416 KB |
Output is correct |
24 |
Correct |
14 ms |
35416 KB |
Output is correct |
25 |
Correct |
37 ms |
35444 KB |
Output is correct |
26 |
Correct |
14 ms |
35420 KB |
Output is correct |
27 |
Correct |
14 ms |
35420 KB |
Output is correct |
28 |
Correct |
17 ms |
35420 KB |
Output is correct |
29 |
Correct |
23 ms |
35440 KB |
Output is correct |
30 |
Correct |
23 ms |
35420 KB |
Output is correct |
31 |
Correct |
26 ms |
35480 KB |
Output is correct |
32 |
Correct |
29 ms |
35464 KB |
Output is correct |
33 |
Correct |
28 ms |
35420 KB |
Output is correct |
34 |
Correct |
15 ms |
35464 KB |
Output is correct |
35 |
Correct |
15 ms |
35472 KB |
Output is correct |
36 |
Correct |
18 ms |
35420 KB |
Output is correct |
37 |
Correct |
22 ms |
35420 KB |
Output is correct |
38 |
Correct |
26 ms |
35460 KB |
Output is correct |
39 |
Execution timed out |
3007 ms |
41544 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |