#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[200005];
int ret = 1e9;
int size[200005], maxtree[200005];
int kill[200005];
int k;
vector<int> new_vis;
int dfs(int p, int pa){
if(kill[p]) return 0;
new_vis.push_back(p);
int cs = 1;
int maxv = 0;
for (int i=0; i<graph[p].size(); i++) {
if(graph[p][i].second == pa) continue;
int t = dfs(graph[p][i].second,p);
maxv = max(t,maxv);
cs += t;
}
maxtree[p] = maxv;
return size[p] = cs;
}
int get_mid(int p){
new_vis.clear();
memset(size,0,sizeof(size));
memset(maxtree,0,sizeof(maxtree));
int full = dfs(p,-1);
int mid_pos = 0, mid_res =1e9;
for (int i=0; i<new_vis.size(); i++) {
maxtree[new_vis[i]] = max(maxtree[new_vis[i]],full - size[new_vis[i]]);
if(mid_res > maxtree[new_vis[i]]){
mid_pos = new_vis[i];
mid_res = maxtree[mid_pos];
}
}
return mid_pos;
}
int *v;
void solve(int p){
int mid = get_mid(p);
kill[mid] = 1;
memset(v,63,sizeof(v));
v[0] = 0;
for (int i=0; i<graph[mid].size(); i++) {
if(kill[graph[mid][i].second]) continue;
queue<int> q,d,p,l;
vector<int> cd1, cd2;
if(graph[mid][i].first > k) continue;
q.push(graph[mid][i].second);
d.push(graph[mid][i].first);
l.push(1);
p.push(mid);
while (!q.empty()) {
int qf = q.front();
int df = d.front();
int pf = p.front();
int lf = l.front();
cd1.push_back(df);
cd2.push_back(lf);
ret = min(v[k-df] + lf,ret);
q.pop();
d.pop();
p.pop();
l.pop();
for (int i=0; i<graph[qf].size(); i++) {
int pos = graph[qf][i].second;
if(kill[pos] || pos == pf) continue;
if(df + graph[qf][i].first > k) continue;
q.push(pos);
d.push(df + graph[qf][i].first);
p.push(qf);
l.push(lf + 1);
}
}
for (int i=0; i<cd1.size(); i++) {
v[cd1[i]] = min(v[cd1[i]],cd2[i]);
}
}
for (int i=0; i<graph[mid].size(); i++) {
if(kill[graph[mid][i].second]) continue;
solve(graph[mid][i].second);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i=0; i<N-1; i++) {
graph[H[i][0]].push_back(pi(L[i],H[i][1]));
graph[H[i][1]].push_back(pi(L[i],H[i][0]));
}
v = (int* )calloc(K+1,sizeof(int));
k = K;
solve(0);
if(ret > 1e8) return -1;
return ret;
}
Compilation message
race.cpp: In function 'int dfs(int, int)':
race.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[p].size(); i++) {
~^~~~~~~~~~~~~~~~
race.cpp: In function 'int get_mid(int)':
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<new_vis.size(); i++) {
~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:56:23: warning: argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
memset(v,63,sizeof(v));
^
race.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[mid].size(); i++) {
~^~~~~~~~~~~~~~~~~~
race.cpp:79:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[qf].size(); i++) {
~^~~~~~~~~~~~~~~~~
race.cpp:89:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<cd1.size(); i++) {
~^~~~~~~~~~~
race.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[mid].size(); i++) {
~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
