#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
//#include "race.h"
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const int inf=1e9,MAXN=2e5+5;
vpi g[MAXN]; set<pair<ll,int>> st[MAXN];
int ans;
void dfs(int v,int p,int d,int k,ll curr = 0) {
for(auto [u,w] : g[v]) {
if(u == p) continue;
dfs(u,v,d+1,k,curr+w);
if(st[v].size() < st[u].size()) swap(st[u],st[v]);
for(auto x : st[u]) {
auto y = st[v].lower_bound({k-x.fi+2*curr,0});
if(y != st[v].end() and (*y).fi == k-x.fi+2*curr) ans = min(ans,(*y).se + x.se - 2 * d);
}
for(auto x : st[u]) st[v].ins(x);
}
auto x = st[v].lower_bound({curr+k,0});
if(x != st[v].end() and (*x).fi == curr+k) ans = min(ans,(*x).se - d);
st[v].ins({curr,d});
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = inf;
for(int i=0;i<N;i++) g[i].clear(),st[i].clear();
for(int i=0;i<N-1;i++) {
g[H[i][0]].pb({H[i][1],L[i]});
g[H[i][1]].pb({H[i][0],L[i]});
}
dfs(0,-1,0,K);
return (ans == inf ? -1 : ans);
}
/* int main() {
send help
int H[][2] = { {0,1}, {0,2} };
int L[] = {2,2};
printl(best_path(3,4,H,L));
return 0;
} */
Compilation message
race.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
1 | #pragma gcc diagnostic "-std=c++1z"
|
race.cpp: In function 'void dfs(int, int, int, int, ll)':
race.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | for(auto [u,w] : g[v]) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18008 KB |
Output is correct |
2 |
Correct |
4 ms |
18012 KB |
Output is correct |
3 |
Correct |
3 ms |
18012 KB |
Output is correct |
4 |
Correct |
4 ms |
18012 KB |
Output is correct |
5 |
Correct |
3 ms |
18012 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18104 KB |
Output is correct |
8 |
Correct |
3 ms |
18180 KB |
Output is correct |
9 |
Correct |
3 ms |
18012 KB |
Output is correct |
10 |
Correct |
3 ms |
18012 KB |
Output is correct |
11 |
Correct |
3 ms |
18160 KB |
Output is correct |
12 |
Correct |
3 ms |
18008 KB |
Output is correct |
13 |
Correct |
3 ms |
18008 KB |
Output is correct |
14 |
Correct |
4 ms |
18156 KB |
Output is correct |
15 |
Correct |
3 ms |
18012 KB |
Output is correct |
16 |
Correct |
3 ms |
18012 KB |
Output is correct |
17 |
Correct |
4 ms |
18008 KB |
Output is correct |
18 |
Correct |
4 ms |
18012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18008 KB |
Output is correct |
2 |
Correct |
4 ms |
18012 KB |
Output is correct |
3 |
Correct |
3 ms |
18012 KB |
Output is correct |
4 |
Correct |
4 ms |
18012 KB |
Output is correct |
5 |
Correct |
3 ms |
18012 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18104 KB |
Output is correct |
8 |
Correct |
3 ms |
18180 KB |
Output is correct |
9 |
Correct |
3 ms |
18012 KB |
Output is correct |
10 |
Correct |
3 ms |
18012 KB |
Output is correct |
11 |
Correct |
3 ms |
18160 KB |
Output is correct |
12 |
Correct |
3 ms |
18008 KB |
Output is correct |
13 |
Correct |
3 ms |
18008 KB |
Output is correct |
14 |
Correct |
4 ms |
18156 KB |
Output is correct |
15 |
Correct |
3 ms |
18012 KB |
Output is correct |
16 |
Correct |
3 ms |
18012 KB |
Output is correct |
17 |
Correct |
4 ms |
18008 KB |
Output is correct |
18 |
Correct |
4 ms |
18012 KB |
Output is correct |
19 |
Correct |
3 ms |
18012 KB |
Output is correct |
20 |
Correct |
3 ms |
18176 KB |
Output is correct |
21 |
Correct |
4 ms |
18268 KB |
Output is correct |
22 |
Correct |
3 ms |
18268 KB |
Output is correct |
23 |
Correct |
4 ms |
18268 KB |
Output is correct |
24 |
Correct |
4 ms |
18264 KB |
Output is correct |
25 |
Correct |
3 ms |
18268 KB |
Output is correct |
26 |
Correct |
5 ms |
18264 KB |
Output is correct |
27 |
Correct |
4 ms |
18264 KB |
Output is correct |
28 |
Correct |
4 ms |
18268 KB |
Output is correct |
29 |
Correct |
3 ms |
18268 KB |
Output is correct |
30 |
Correct |
6 ms |
18520 KB |
Output is correct |
31 |
Correct |
4 ms |
18268 KB |
Output is correct |
32 |
Correct |
4 ms |
18268 KB |
Output is correct |
33 |
Correct |
4 ms |
18268 KB |
Output is correct |
34 |
Correct |
3 ms |
18180 KB |
Output is correct |
35 |
Correct |
4 ms |
18268 KB |
Output is correct |
36 |
Correct |
4 ms |
18268 KB |
Output is correct |
37 |
Correct |
4 ms |
18268 KB |
Output is correct |
38 |
Correct |
4 ms |
18268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18008 KB |
Output is correct |
2 |
Correct |
4 ms |
18012 KB |
Output is correct |
3 |
Correct |
3 ms |
18012 KB |
Output is correct |
4 |
Correct |
4 ms |
18012 KB |
Output is correct |
5 |
Correct |
3 ms |
18012 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18104 KB |
Output is correct |
8 |
Correct |
3 ms |
18180 KB |
Output is correct |
9 |
Correct |
3 ms |
18012 KB |
Output is correct |
10 |
Correct |
3 ms |
18012 KB |
Output is correct |
11 |
Correct |
3 ms |
18160 KB |
Output is correct |
12 |
Correct |
3 ms |
18008 KB |
Output is correct |
13 |
Correct |
3 ms |
18008 KB |
Output is correct |
14 |
Correct |
4 ms |
18156 KB |
Output is correct |
15 |
Correct |
3 ms |
18012 KB |
Output is correct |
16 |
Correct |
3 ms |
18012 KB |
Output is correct |
17 |
Correct |
4 ms |
18008 KB |
Output is correct |
18 |
Correct |
4 ms |
18012 KB |
Output is correct |
19 |
Correct |
94 ms |
41352 KB |
Output is correct |
20 |
Correct |
82 ms |
41476 KB |
Output is correct |
21 |
Correct |
86 ms |
41044 KB |
Output is correct |
22 |
Correct |
77 ms |
40016 KB |
Output is correct |
23 |
Correct |
121 ms |
54872 KB |
Output is correct |
24 |
Correct |
82 ms |
43856 KB |
Output is correct |
25 |
Correct |
81 ms |
43948 KB |
Output is correct |
26 |
Correct |
59 ms |
49744 KB |
Output is correct |
27 |
Correct |
139 ms |
46732 KB |
Output is correct |
28 |
Correct |
158 ms |
79696 KB |
Output is correct |
29 |
Correct |
149 ms |
77828 KB |
Output is correct |
30 |
Correct |
129 ms |
46728 KB |
Output is correct |
31 |
Correct |
130 ms |
46772 KB |
Output is correct |
32 |
Correct |
167 ms |
46936 KB |
Output is correct |
33 |
Correct |
109 ms |
42364 KB |
Output is correct |
34 |
Correct |
186 ms |
75344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18008 KB |
Output is correct |
2 |
Correct |
4 ms |
18012 KB |
Output is correct |
3 |
Correct |
3 ms |
18012 KB |
Output is correct |
4 |
Correct |
4 ms |
18012 KB |
Output is correct |
5 |
Correct |
3 ms |
18012 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18104 KB |
Output is correct |
8 |
Correct |
3 ms |
18180 KB |
Output is correct |
9 |
Correct |
3 ms |
18012 KB |
Output is correct |
10 |
Correct |
3 ms |
18012 KB |
Output is correct |
11 |
Correct |
3 ms |
18160 KB |
Output is correct |
12 |
Correct |
3 ms |
18008 KB |
Output is correct |
13 |
Correct |
3 ms |
18008 KB |
Output is correct |
14 |
Correct |
4 ms |
18156 KB |
Output is correct |
15 |
Correct |
3 ms |
18012 KB |
Output is correct |
16 |
Correct |
3 ms |
18012 KB |
Output is correct |
17 |
Correct |
4 ms |
18008 KB |
Output is correct |
18 |
Correct |
4 ms |
18012 KB |
Output is correct |
19 |
Correct |
3 ms |
18012 KB |
Output is correct |
20 |
Correct |
3 ms |
18176 KB |
Output is correct |
21 |
Correct |
4 ms |
18268 KB |
Output is correct |
22 |
Correct |
3 ms |
18268 KB |
Output is correct |
23 |
Correct |
4 ms |
18268 KB |
Output is correct |
24 |
Correct |
4 ms |
18264 KB |
Output is correct |
25 |
Correct |
3 ms |
18268 KB |
Output is correct |
26 |
Correct |
5 ms |
18264 KB |
Output is correct |
27 |
Correct |
4 ms |
18264 KB |
Output is correct |
28 |
Correct |
4 ms |
18268 KB |
Output is correct |
29 |
Correct |
3 ms |
18268 KB |
Output is correct |
30 |
Correct |
6 ms |
18520 KB |
Output is correct |
31 |
Correct |
4 ms |
18268 KB |
Output is correct |
32 |
Correct |
4 ms |
18268 KB |
Output is correct |
33 |
Correct |
4 ms |
18268 KB |
Output is correct |
34 |
Correct |
3 ms |
18180 KB |
Output is correct |
35 |
Correct |
4 ms |
18268 KB |
Output is correct |
36 |
Correct |
4 ms |
18268 KB |
Output is correct |
37 |
Correct |
4 ms |
18268 KB |
Output is correct |
38 |
Correct |
4 ms |
18268 KB |
Output is correct |
39 |
Correct |
94 ms |
41352 KB |
Output is correct |
40 |
Correct |
82 ms |
41476 KB |
Output is correct |
41 |
Correct |
86 ms |
41044 KB |
Output is correct |
42 |
Correct |
77 ms |
40016 KB |
Output is correct |
43 |
Correct |
121 ms |
54872 KB |
Output is correct |
44 |
Correct |
82 ms |
43856 KB |
Output is correct |
45 |
Correct |
81 ms |
43948 KB |
Output is correct |
46 |
Correct |
59 ms |
49744 KB |
Output is correct |
47 |
Correct |
139 ms |
46732 KB |
Output is correct |
48 |
Correct |
158 ms |
79696 KB |
Output is correct |
49 |
Correct |
149 ms |
77828 KB |
Output is correct |
50 |
Correct |
129 ms |
46728 KB |
Output is correct |
51 |
Correct |
130 ms |
46772 KB |
Output is correct |
52 |
Correct |
167 ms |
46936 KB |
Output is correct |
53 |
Correct |
109 ms |
42364 KB |
Output is correct |
54 |
Correct |
186 ms |
75344 KB |
Output is correct |
55 |
Correct |
11 ms |
21080 KB |
Output is correct |
56 |
Correct |
9 ms |
19800 KB |
Output is correct |
57 |
Correct |
52 ms |
36888 KB |
Output is correct |
58 |
Correct |
33 ms |
31428 KB |
Output is correct |
59 |
Correct |
59 ms |
49804 KB |
Output is correct |
60 |
Correct |
135 ms |
78420 KB |
Output is correct |
61 |
Correct |
161 ms |
52564 KB |
Output is correct |
62 |
Correct |
135 ms |
46932 KB |
Output is correct |
63 |
Correct |
137 ms |
46932 KB |
Output is correct |
64 |
Correct |
285 ms |
103148 KB |
Output is correct |
65 |
Correct |
276 ms |
96336 KB |
Output is correct |
66 |
Correct |
160 ms |
73812 KB |
Output is correct |
67 |
Correct |
96 ms |
43972 KB |
Output is correct |
68 |
Correct |
237 ms |
64340 KB |
Output is correct |
69 |
Correct |
258 ms |
70224 KB |
Output is correct |
70 |
Correct |
203 ms |
62804 KB |
Output is correct |