이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const int MAXX=1e6+5;
vector<int> g[MAXN], pes[MAXN];
int n, respf;
ll x;
class solution {
public:
int resp=MAXN;
void init() {
tam[n]=0;
memset(prof, 0, sizeof(prof));
fill(best, best+x+2, MAXN);
solve(0, 1);
}
void solve(int cur, int k) {
basic_scan(cur, cur);
cur=find_centroid(cur, cur, tam[cur]);
prof[cur]=k;
// printf(">> %d <<\n", cur);
best[0]=0;
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(prof[viz]) continue;
adv_scan(viz, cur, 1, peso, 0);
adv_scan(viz, cur, 1, peso, 1);
}
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(prof[viz]) continue;
adv_scan(viz, cur, 1, peso, -1);
}
for(auto viz : g[cur]) {
if(prof[viz]) continue;
solve(viz, k+1);
}
}
private:
int tam[MAXN], prof[MAXN];
int best[MAXX];
void basic_scan(int cur, int p) {
tam[cur]=1;
for(auto viz : g[cur]) {
if(viz==p||prof[viz]) continue;
basic_scan(viz, cur);
tam[cur]+=tam[viz];
}
}
void adv_scan(int cur, int p, int d, ll dd, int k) {
if(dd>x) return;
if(k==0) resp=min(resp, d+best[x-dd]);
else if(k==1) best[dd]=min(best[dd], d);
else best[dd]=MAXN;
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(viz==p||prof[viz]) continue;
adv_scan(viz, cur, d+1, dd+peso, k);
}
}
int find_centroid(int cur, int p, int val) {
int grande=n;
for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz;
if(tam[grande]*2<=val) return cur;
return find_centroid(grande, cur, val);
}
};
int best_path(int N, int K, int H[][2], int L[])
{
n=N; x=K;
for(int i=0; i<n-1; i++) {
int a=H[i][0]; int b=H[i][1];
g[a].push_back(b); pes[a].push_back(L[i]);
g[b].push_back(a); pes[b].push_back(L[i]);
}
solution sol;
sol.init();
respf=sol.resp;
if(respf>n) respf=-1;
return respf;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].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... |