# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990184 |
2024-05-29T19:53:52 Z |
hasan2006 |
Race (IOI11_race) |
C++17 |
|
754 ms |
62800 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] , c[N] , d[N] , sz[N] , us[N];
vector<pair<int,int>>v[N];
int dfs_sz(int n , int par = 0){
sz[n] = 1;
for(auto to : v[n])
if(!us[to.fi] && to.fi != par)
sz[n] += dfs_sz(to.fi , n);
return sz[n];
}
ll ans = 1e9 , k;
int get_centroid(int n , int par , int s){
for(auto to : v[n])
if(!us[to.fi] && to.fi != par && sz[to.fi] > s / 2)
return get_centroid(to.fi , n , s);
return n;
}
set<pair<ll,ll>>st,st1;
void dfs(int n , int par, ll dis , ll cnt){
st1.insert({dis , cnt});
auto it = st.lower_bound({k - dis , 0});
if(it != st.end() && it->fi == k - dis)
ans = min(ans , cnt + it->se);
for(auto to : v[n])
if(!us[to.fi] && to.fi != par)
dfs(to.fi , n , dis + to.se , cnt + 1);
}
void centroid(int n){
int x = get_centroid(n , 0 , dfs_sz(n));
us[x] = 1;
st.clear();
st.insert({0 , 0});
for(auto to : v[x]){
if(!us[to.fi]){
st1.clear();
dfs(to.fi , x , to.se , 1);
for(auto it : st1)
st.insert(it);
}
}
for(auto to : v[x])
if(!us[to.fi])
centroid(to.fi);
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for(int i = 0; i < N - 1; i++) {
int x = H[i][0] + 1,y = H[i][1] + 1;
v[x].pb({y, L[i]});
v[y].pb({x, L[i]});
}
centroid(1);
if(ans > N)
ans = -1;
return ans;
}
// Author : حسن
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18780 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
2 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18776 KB |
Output is correct |
9 |
Correct |
3 ms |
18780 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18776 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
3 ms |
18776 KB |
Output is correct |
16 |
Correct |
3 ms |
18876 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
3 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18780 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
2 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18776 KB |
Output is correct |
9 |
Correct |
3 ms |
18780 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18776 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
3 ms |
18776 KB |
Output is correct |
16 |
Correct |
3 ms |
18876 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
3 ms |
18780 KB |
Output is correct |
19 |
Correct |
3 ms |
18776 KB |
Output is correct |
20 |
Correct |
3 ms |
18780 KB |
Output is correct |
21 |
Correct |
3 ms |
18780 KB |
Output is correct |
22 |
Correct |
4 ms |
19036 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
3 ms |
18780 KB |
Output is correct |
25 |
Correct |
4 ms |
18776 KB |
Output is correct |
26 |
Correct |
4 ms |
18952 KB |
Output is correct |
27 |
Correct |
3 ms |
18776 KB |
Output is correct |
28 |
Correct |
4 ms |
18776 KB |
Output is correct |
29 |
Correct |
4 ms |
18780 KB |
Output is correct |
30 |
Correct |
4 ms |
19028 KB |
Output is correct |
31 |
Correct |
4 ms |
18780 KB |
Output is correct |
32 |
Correct |
4 ms |
18780 KB |
Output is correct |
33 |
Correct |
4 ms |
18780 KB |
Output is correct |
34 |
Correct |
4 ms |
19036 KB |
Output is correct |
35 |
Correct |
4 ms |
18780 KB |
Output is correct |
36 |
Correct |
3 ms |
19024 KB |
Output is correct |
37 |
Correct |
4 ms |
18780 KB |
Output is correct |
38 |
Correct |
5 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18780 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
2 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18776 KB |
Output is correct |
9 |
Correct |
3 ms |
18780 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18776 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
3 ms |
18776 KB |
Output is correct |
16 |
Correct |
3 ms |
18876 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
3 ms |
18780 KB |
Output is correct |
19 |
Correct |
181 ms |
25028 KB |
Output is correct |
20 |
Correct |
182 ms |
24984 KB |
Output is correct |
21 |
Correct |
172 ms |
24980 KB |
Output is correct |
22 |
Correct |
149 ms |
25004 KB |
Output is correct |
23 |
Correct |
243 ms |
25424 KB |
Output is correct |
24 |
Correct |
97 ms |
24920 KB |
Output is correct |
25 |
Correct |
331 ms |
38112 KB |
Output is correct |
26 |
Correct |
258 ms |
40588 KB |
Output is correct |
27 |
Correct |
204 ms |
36176 KB |
Output is correct |
28 |
Correct |
704 ms |
62800 KB |
Output is correct |
29 |
Correct |
697 ms |
62296 KB |
Output is correct |
30 |
Correct |
210 ms |
36688 KB |
Output is correct |
31 |
Correct |
265 ms |
36832 KB |
Output is correct |
32 |
Correct |
227 ms |
36444 KB |
Output is correct |
33 |
Correct |
307 ms |
32588 KB |
Output is correct |
34 |
Correct |
558 ms |
48208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18776 KB |
Output is correct |
2 |
Correct |
3 ms |
18780 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
3 ms |
18780 KB |
Output is correct |
7 |
Correct |
2 ms |
18780 KB |
Output is correct |
8 |
Correct |
3 ms |
18776 KB |
Output is correct |
9 |
Correct |
3 ms |
18780 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18776 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18780 KB |
Output is correct |
15 |
Correct |
3 ms |
18776 KB |
Output is correct |
16 |
Correct |
3 ms |
18876 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
3 ms |
18780 KB |
Output is correct |
19 |
Correct |
3 ms |
18776 KB |
Output is correct |
20 |
Correct |
3 ms |
18780 KB |
Output is correct |
21 |
Correct |
3 ms |
18780 KB |
Output is correct |
22 |
Correct |
4 ms |
19036 KB |
Output is correct |
23 |
Correct |
4 ms |
19036 KB |
Output is correct |
24 |
Correct |
3 ms |
18780 KB |
Output is correct |
25 |
Correct |
4 ms |
18776 KB |
Output is correct |
26 |
Correct |
4 ms |
18952 KB |
Output is correct |
27 |
Correct |
3 ms |
18776 KB |
Output is correct |
28 |
Correct |
4 ms |
18776 KB |
Output is correct |
29 |
Correct |
4 ms |
18780 KB |
Output is correct |
30 |
Correct |
4 ms |
19028 KB |
Output is correct |
31 |
Correct |
4 ms |
18780 KB |
Output is correct |
32 |
Correct |
4 ms |
18780 KB |
Output is correct |
33 |
Correct |
4 ms |
18780 KB |
Output is correct |
34 |
Correct |
4 ms |
19036 KB |
Output is correct |
35 |
Correct |
4 ms |
18780 KB |
Output is correct |
36 |
Correct |
3 ms |
19024 KB |
Output is correct |
37 |
Correct |
4 ms |
18780 KB |
Output is correct |
38 |
Correct |
5 ms |
18780 KB |
Output is correct |
39 |
Correct |
181 ms |
25028 KB |
Output is correct |
40 |
Correct |
182 ms |
24984 KB |
Output is correct |
41 |
Correct |
172 ms |
24980 KB |
Output is correct |
42 |
Correct |
149 ms |
25004 KB |
Output is correct |
43 |
Correct |
243 ms |
25424 KB |
Output is correct |
44 |
Correct |
97 ms |
24920 KB |
Output is correct |
45 |
Correct |
331 ms |
38112 KB |
Output is correct |
46 |
Correct |
258 ms |
40588 KB |
Output is correct |
47 |
Correct |
204 ms |
36176 KB |
Output is correct |
48 |
Correct |
704 ms |
62800 KB |
Output is correct |
49 |
Correct |
697 ms |
62296 KB |
Output is correct |
50 |
Correct |
210 ms |
36688 KB |
Output is correct |
51 |
Correct |
265 ms |
36832 KB |
Output is correct |
52 |
Correct |
227 ms |
36444 KB |
Output is correct |
53 |
Correct |
307 ms |
32588 KB |
Output is correct |
54 |
Correct |
558 ms |
48208 KB |
Output is correct |
55 |
Correct |
19 ms |
20060 KB |
Output is correct |
56 |
Correct |
13 ms |
19152 KB |
Output is correct |
57 |
Correct |
113 ms |
25260 KB |
Output is correct |
58 |
Correct |
30 ms |
25960 KB |
Output is correct |
59 |
Correct |
281 ms |
40588 KB |
Output is correct |
60 |
Correct |
754 ms |
62524 KB |
Output is correct |
61 |
Correct |
238 ms |
40016 KB |
Output is correct |
62 |
Correct |
219 ms |
36688 KB |
Output is correct |
63 |
Correct |
214 ms |
36436 KB |
Output is correct |
64 |
Correct |
662 ms |
46928 KB |
Output is correct |
65 |
Correct |
478 ms |
47444 KB |
Output is correct |
66 |
Correct |
687 ms |
58192 KB |
Output is correct |
67 |
Correct |
68 ms |
34872 KB |
Output is correct |
68 |
Correct |
302 ms |
46040 KB |
Output is correct |
69 |
Correct |
307 ms |
44112 KB |
Output is correct |
70 |
Correct |
323 ms |
45192 KB |
Output is correct |