#include "race.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int N,K;
int H[200001][2];
int L[200001];
int subsize[200001];
vector<pair<int,int>>adj[200001];
bool dead[200001];
ll dp[1000001]; //min edges to obtain length i
ll temp[1000001];
ll ans=INF;
int dfs(int node, int par){
subsize[node]=1;
for (int i=0;i<(int)adj[node].size();i++){
int v=adj[node][i].first;
if (!dead[v] && v!=par)
subsize[node]+=dfs(v,node);
}
return subsize[node];
}
int dfs(int node, int par, int size){
for (int i=0;i<(int)adj[node].size();i++){
int v=adj[node][i].first;
if (!dead[v] && v!=par && subsize[v]>size/2)
return dfs(v,node,size);
}
return node;
}
void dfs2(int node, int par, int numEdges, ll dis){
if (dis>K)
return;
temp[dis]=min(temp[dis],(ll)numEdges);
for (int i=0;i<(int)adj[node].size();i++){
int v=adj[node][i].first;
if (!dead[v] && v!=par)
dfs2(v,node,numEdges+1,dis+adj[node][i].second);
}
}
void solve(int node){
int size=dfs(node,node);
int centroid=dfs(node,node,size);
dead[centroid]=true;
for (int i=1;i<=K;i++)
dp[i]=INF;
for (int i=0;i<(int)adj[centroid].size();i++){
int v=adj[centroid][i].first;
if (!dead[v]){
for (int i=1;i<=K;i++)
temp[i]=INF;
temp[0]=0;
dfs2(v,centroid,1,adj[centroid][i].second);
for (int j=1;j<=K;j++)
ans=min(ans,temp[j]+dp[K-j]);
for (int j=1;j<=K;j++)
dp[j]=min(dp[j],temp[j]);
}
}
for (int i=0;i<(int)adj[centroid].size();i++){
int v=adj[centroid][i].first;
if (!dead[v])
solve(v);
}
}
int best_path(int n, int k, int H[][2], int L[]){
N=n;
K=k;
for (int i=0;i+1<N;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
solve(0);
if (ans==INF)
return -1;
else
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
5 ms |
4992 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Execution timed out |
3002 ms |
19584 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
149 ms |
10488 KB |
Output is correct |
20 |
Correct |
174 ms |
10360 KB |
Output is correct |
21 |
Correct |
182 ms |
10488 KB |
Output is correct |
22 |
Correct |
146 ms |
10488 KB |
Output is correct |
23 |
Correct |
122 ms |
10680 KB |
Output is correct |
24 |
Correct |
109 ms |
10616 KB |
Output is correct |
25 |
Correct |
192 ms |
12476 KB |
Output is correct |
26 |
Correct |
112 ms |
14584 KB |
Output is correct |
27 |
Correct |
254 ms |
15992 KB |
Output is correct |
28 |
Correct |
483 ms |
24056 KB |
Output is correct |
29 |
Correct |
461 ms |
23368 KB |
Output is correct |
30 |
Correct |
263 ms |
15864 KB |
Output is correct |
31 |
Correct |
247 ms |
15992 KB |
Output is correct |
32 |
Correct |
325 ms |
15992 KB |
Output is correct |
33 |
Correct |
344 ms |
14776 KB |
Output is correct |
34 |
Correct |
373 ms |
14712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
5120 KB |
Output is correct |
10 |
Correct |
5 ms |
5120 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
5 ms |
4992 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Execution timed out |
3002 ms |
19584 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |