#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXK = 1e6;
const int INF = 987654321;
int N, K, ans=987654321;
vector<pii> adj[MAXN+10];
int sz[MAXN+10];
bool del[MAXN+10];
int M[MAXK+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int tot)
{
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(tot/2<sz[nxt.first]) return getcen(nxt.first, now, tot);
}
return now;
}
void dfs(int now, int bef, int dep, int len, vector<pii>& V)
{
V.push_back({len, dep});
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(len+nxt.second>K) continue;
dfs(nxt.first, now, dep+1, len+nxt.second, V);
}
}
void decomp(int now)
{
int i, j;
getsz(now, now);
now=getcen(now, now, sz[now]);
del[now]=true;
vector<int> change;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
vector<pii> V;
dfs(nxt.first, nxt.first, 1, nxt.second, V);
for(i=0; i<V.size(); i++)
{
int len=V[i].first, dep=V[i].second;
change.push_back(len);
ans=min(ans, M[K-len]+dep);
}
for(i=0; i<V.size(); i++)
{
int len=V[i].first, dep=V[i].second;
M[len]=min(M[len], dep);
}
}
for(i=0; i<change.size(); i++) M[change[i]]=INF;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first);
}
}
int best_path(int NN, int KK, int HH[][2], int LL[])
{
int i, j;
N=NN; K=KK;
for(i=0; i+1<N; i++)
{
int u=HH[i][0], v=HH[i][1], w=LL[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(i=0; i<=1000000; i++) M[i]=INF;
decomp(0);
if(ans==INF) ans=-1;
return ans;
}
Compilation message
race.cpp: In function 'void decomp(int)':
race.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size(); i++)
~^~~~~~~~~
race.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size(); i++)
~^~~~~~~~~
race.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<change.size(); i++) M[change[i]]=INF;
~^~~~~~~~~~~~~~
race.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:95:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8952 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8952 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8952 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8952 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8952 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8952 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8952 KB |
Output is correct |
5 |
Incorrect |
10 ms |
8952 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |