#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define MAX_N 500000
int N, K;
int HH[MAX_N][2];
int LL[MAX_N];
using namespace std;
typedef int ll;
vector <pair <ll, ll> > ND[500005];
ll A[500005];
queue <pair <ll, ll> > Q;
ll P, PV;
vector <pair <ll, ll> > NG;
ll find_mp(ll k, ll pk, ll n){
vector <pair <ll, ll> > PG;
ll m=0, s=0;
for (ll i=0; i<ND[k].size(); i++) {
ll nk = ND[k][i].first;
if (pk == nk or A[nk]) continue;
ll v = find_mp(nk, k, n);
m = max(m, v);
s += v;
PG.push_back({nk, v});
}
if(pk!=-1){
m = max(m, n-s-1);
PG.push_back({pk, n-s-1});
}
//cout<<k<<" "<<s<<" "<<m<<"\n";
if (PV>m) {
PV = m;
P = k;
NG = move(PG);
}
return s+1;
}
ll M[2000005];
ll rez = INT_MAX;
vector <pair<ll,ll> > V;
void path(ll id, ll pid, ll v, ll d){
if(v>K) return;
//cout<<id<<" "<<v<<" "<<d<<"\n" ;
V.push_back({v,d});
if(M[K-v]!=INT_MAX) rez = min(rez, M[K-v]+d);
for(ll i=0; i<ND[id].size(); i++){
ll nid = ND[id][i].first;
ll nv = ND[id][i].second;
if(pid == nid or A[nid]) continue;
path(nid, id, v+nv, d+1);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
N=n;
K=k;
for(ll i=0;i<n-1;i++){
ND[H[i][0]].push_back({H[i][1], L[i]});
ND[H[i][1]].push_back({H[i][0], L[i]});
}
Q.push({0, n});
while (!Q.empty()){
PV=INT_MAX;
ll sz = Q.front().second;
find_mp(Q.front().first, -1, sz);
Q.pop();
A[P] = 1;
for (ll i=0; i<NG.size(); i++){
if(NG[i].second>1)Q.push({NG[i].first, NG[i].second});
}
//cout<<P<<"\n";
for(ll i=0; i<=K; i++){
M[i] = INT_MAX;
}
M[0]=0;
for(ll i=0; i<ND[P].size(); i++){
ll ni = ND[P][i].first;
ll nv = ND[P][i].second;
//cout<<"hello\n";
path(ni, -1, nv, 1);
for(ll j=0; j<V.size(); j++) M[V[j].first]=min(M[V[j].first], V[j].second);
V.clear();
}
//for(ll i=0;i<=K;i++) cout<<(M[i]==INT_MAX?-1:M[i])<<" "; cout<<"\n";
//cout<<rez<<"\n__________\n";
}
return rez==INT_MAX?-1:rez;
}
/*int main()
{
//freopen("in.txt", "r", stdin);
ifstream cin("in.in");
cin>>N>>K;
for(ll i=0;i<N-1;i++){
cin>>HH[i][0]>>HH[i][1]>>LL[i];
}
ll ans = best_path(N, K, HH, LL);
cout<<ans;
}*/
Compilation message
race.cpp: In function 'll find_mp(ll, ll, ll)':
race.cpp:28:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (ll i=0; i<ND[k].size(); i++) {
| ~^~~~~~~~~~~~~
race.cpp: In function 'void path(ll, ll, ll, ll)':
race.cpp:58:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(ll i=0; i<ND[id].size(); i++){
| ~^~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:83:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (ll i=0; i<NG.size(); i++){
| ~^~~~~~~~~~
race.cpp:92:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(ll i=0; i<ND[P].size(); i++){
| ~^~~~~~~~~~~~~
race.cpp:97:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(ll j=0; j<V.size(); j++) M[V[j].first]=min(M[V[j].first], V[j].second);
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
4 ms |
20828 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
4 ms |
20828 KB |
Output is correct |
6 |
Correct |
4 ms |
20828 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
4 ms |
20828 KB |
Output is correct |
10 |
Correct |
4 ms |
20828 KB |
Output is correct |
11 |
Correct |
4 ms |
20828 KB |
Output is correct |
12 |
Correct |
4 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
20828 KB |
Output is correct |
14 |
Correct |
4 ms |
20824 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20824 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
4 ms |
20828 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
4 ms |
20828 KB |
Output is correct |
6 |
Correct |
4 ms |
20828 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
4 ms |
20828 KB |
Output is correct |
10 |
Correct |
4 ms |
20828 KB |
Output is correct |
11 |
Correct |
4 ms |
20828 KB |
Output is correct |
12 |
Correct |
4 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
20828 KB |
Output is correct |
14 |
Correct |
4 ms |
20824 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20824 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
4 ms |
20828 KB |
Output is correct |
20 |
Correct |
4 ms |
20828 KB |
Output is correct |
21 |
Correct |
5 ms |
20828 KB |
Output is correct |
22 |
Correct |
37 ms |
24924 KB |
Output is correct |
23 |
Correct |
31 ms |
24920 KB |
Output is correct |
24 |
Correct |
33 ms |
25056 KB |
Output is correct |
25 |
Correct |
32 ms |
24924 KB |
Output is correct |
26 |
Correct |
15 ms |
22872 KB |
Output is correct |
27 |
Correct |
31 ms |
24924 KB |
Output is correct |
28 |
Correct |
11 ms |
22876 KB |
Output is correct |
29 |
Correct |
15 ms |
23064 KB |
Output is correct |
30 |
Correct |
16 ms |
22872 KB |
Output is correct |
31 |
Correct |
26 ms |
24920 KB |
Output is correct |
32 |
Correct |
28 ms |
24924 KB |
Output is correct |
33 |
Correct |
32 ms |
24924 KB |
Output is correct |
34 |
Correct |
30 ms |
23052 KB |
Output is correct |
35 |
Correct |
37 ms |
24924 KB |
Output is correct |
36 |
Correct |
38 ms |
24924 KB |
Output is correct |
37 |
Correct |
31 ms |
25116 KB |
Output is correct |
38 |
Correct |
25 ms |
22876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
4 ms |
20828 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
4 ms |
20828 KB |
Output is correct |
6 |
Correct |
4 ms |
20828 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
4 ms |
20828 KB |
Output is correct |
10 |
Correct |
4 ms |
20828 KB |
Output is correct |
11 |
Correct |
4 ms |
20828 KB |
Output is correct |
12 |
Correct |
4 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
20828 KB |
Output is correct |
14 |
Correct |
4 ms |
20824 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20824 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
129 ms |
26964 KB |
Output is correct |
20 |
Correct |
123 ms |
26964 KB |
Output is correct |
21 |
Correct |
125 ms |
27216 KB |
Output is correct |
22 |
Correct |
125 ms |
27344 KB |
Output is correct |
23 |
Correct |
115 ms |
27220 KB |
Output is correct |
24 |
Correct |
59 ms |
26960 KB |
Output is correct |
25 |
Correct |
157 ms |
33024 KB |
Output is correct |
26 |
Correct |
122 ms |
39380 KB |
Output is correct |
27 |
Correct |
156 ms |
30804 KB |
Output is correct |
28 |
Correct |
302 ms |
54832 KB |
Output is correct |
29 |
Correct |
315 ms |
53080 KB |
Output is correct |
30 |
Correct |
148 ms |
30800 KB |
Output is correct |
31 |
Correct |
153 ms |
30772 KB |
Output is correct |
32 |
Correct |
289 ms |
30800 KB |
Output is correct |
33 |
Correct |
232 ms |
30040 KB |
Output is correct |
34 |
Correct |
285 ms |
30008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
20828 KB |
Output is correct |
2 |
Correct |
4 ms |
20828 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
4 ms |
20828 KB |
Output is correct |
6 |
Correct |
4 ms |
20828 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
4 ms |
20828 KB |
Output is correct |
10 |
Correct |
4 ms |
20828 KB |
Output is correct |
11 |
Correct |
4 ms |
20828 KB |
Output is correct |
12 |
Correct |
4 ms |
20828 KB |
Output is correct |
13 |
Correct |
4 ms |
20828 KB |
Output is correct |
14 |
Correct |
4 ms |
20824 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20824 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
4 ms |
20828 KB |
Output is correct |
20 |
Correct |
4 ms |
20828 KB |
Output is correct |
21 |
Correct |
5 ms |
20828 KB |
Output is correct |
22 |
Correct |
37 ms |
24924 KB |
Output is correct |
23 |
Correct |
31 ms |
24920 KB |
Output is correct |
24 |
Correct |
33 ms |
25056 KB |
Output is correct |
25 |
Correct |
32 ms |
24924 KB |
Output is correct |
26 |
Correct |
15 ms |
22872 KB |
Output is correct |
27 |
Correct |
31 ms |
24924 KB |
Output is correct |
28 |
Correct |
11 ms |
22876 KB |
Output is correct |
29 |
Correct |
15 ms |
23064 KB |
Output is correct |
30 |
Correct |
16 ms |
22872 KB |
Output is correct |
31 |
Correct |
26 ms |
24920 KB |
Output is correct |
32 |
Correct |
28 ms |
24924 KB |
Output is correct |
33 |
Correct |
32 ms |
24924 KB |
Output is correct |
34 |
Correct |
30 ms |
23052 KB |
Output is correct |
35 |
Correct |
37 ms |
24924 KB |
Output is correct |
36 |
Correct |
38 ms |
24924 KB |
Output is correct |
37 |
Correct |
31 ms |
25116 KB |
Output is correct |
38 |
Correct |
25 ms |
22876 KB |
Output is correct |
39 |
Correct |
129 ms |
26964 KB |
Output is correct |
40 |
Correct |
123 ms |
26964 KB |
Output is correct |
41 |
Correct |
125 ms |
27216 KB |
Output is correct |
42 |
Correct |
125 ms |
27344 KB |
Output is correct |
43 |
Correct |
115 ms |
27220 KB |
Output is correct |
44 |
Correct |
59 ms |
26960 KB |
Output is correct |
45 |
Correct |
157 ms |
33024 KB |
Output is correct |
46 |
Correct |
122 ms |
39380 KB |
Output is correct |
47 |
Correct |
156 ms |
30804 KB |
Output is correct |
48 |
Correct |
302 ms |
54832 KB |
Output is correct |
49 |
Correct |
315 ms |
53080 KB |
Output is correct |
50 |
Correct |
148 ms |
30800 KB |
Output is correct |
51 |
Correct |
153 ms |
30772 KB |
Output is correct |
52 |
Correct |
289 ms |
30800 KB |
Output is correct |
53 |
Correct |
232 ms |
30040 KB |
Output is correct |
54 |
Correct |
285 ms |
30008 KB |
Output is correct |
55 |
Correct |
14 ms |
21340 KB |
Output is correct |
56 |
Correct |
13 ms |
21340 KB |
Output is correct |
57 |
Correct |
108 ms |
28116 KB |
Output is correct |
58 |
Correct |
31 ms |
28416 KB |
Output is correct |
59 |
Correct |
962 ms |
41488 KB |
Output is correct |
60 |
Execution timed out |
3022 ms |
58608 KB |
Time limit exceeded |
61 |
Halted |
0 ms |
0 KB |
- |