This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 10, MAXK = 1000000 + 10, INF = 100000000;
vector<int> g[MAXN], p[MAXN];
int marc[MAXN], lastSave[MAXN], removed[MAXN], sub[MAXN];
int ans = INF, cnt, k;
int readMarc(int pos){
if(lastSave[pos] == cnt) return marc[pos];
else return INF;
}
void writeMarc(int pos, int val){
marc[pos] = val; lastSave[pos] = cnt;
}
void preComp(int v, int f){
sub[v] = 1;
for(int i = 0;i<g[v].size();i++){
int viz = g[v][i];
if(viz == f) continue;
preComp(viz, v);
sub[v] += sub[viz];
}
return;
}
int findCentroid(int v){
int centroid = v;
for(int i = 0;i<g[v].size();i++){
int viz = g[v][i];
if(removed[viz] == 1) continue;
if(sub[viz] > sub[v]/2){
sub[v] -= sub[viz];
sub[viz] += sub[v];
centroid = findCentroid(viz);
}
}
return centroid;
}
void computeSubtree(int v, int f, int dist, int edgeCount){
int possible = readMarc(k - dist);
if(possible != INF){
ans = min(ans, possible + edgeCount);
}
for(int i = 0;i<g[v].size();i++){
int viz = g[v][i];
if(viz == f) continue;
computeSubtree(viz, v, dist + p[v][i], edgeCount + 1);
}
if(readMarc(dist) > edgeCount) writeMarc(dist, edgeCount);
}
void doTree(int v){
int centroid = findCentroid(v);
removed[centroid] = 1;
cnt++;
for(int i = 0;i<g[centroid].size();i++){
int viz = g[centroid][i];
if(removed[viz] == 1) continue;
computeSubtree(viz, centroid, p[centroid][i], 1);
}
for(int i = 0;i<g[centroid].size();i++){
int viz = g[centroid][i];
if(removed[viz] == 1) continue;
doTree(viz);
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for(int i = 0;i<N-1;i++){
int a = H[i][0], b = H[i][1];
g[a].push_back(b); g[b].push_back(a);
p[a].push_back(L[i]); p[b].push_back(L[i]);
}
preComp(0, -1);
doTree(0);
if(ans == INF) return -1;
return ans;
}
Compilation message (stderr)
race.cpp: In function 'void preComp(int, int)':
race.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 0;i<g[v].size();i++){
| ~^~~~~~~~~~~~
race.cpp: In function 'int findCentroid(int)':
race.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0;i<g[v].size();i++){
| ~^~~~~~~~~~~~
race.cpp: In function 'void computeSubtree(int, int, int, int)':
race.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0;i<g[v].size();i++){
| ~^~~~~~~~~~~~
race.cpp: In function 'void doTree(int)':
race.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0;i<g[centroid].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
race.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 0;i<g[centroid].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |