이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int nax=2e5+5;
typedef long long ll;
struct node{
int a,c;
ll b;
};
vector<node> grafo[nax];
int centres[nax];
int sizes[nax];
int ans=INT_MAX;
int N,K;
map<ll,int> m;
void incl(int n, int a, int d, ll v){
if(K<v)return;
if(a!=-1){
if(m.count(K-v))ans=min(ans,m[K-v]+d);
if(!m.count(v))m[v]=d;
else m[v]=min(m[v],d);
}else{
m.clear();
}
for(auto x:grafo[n]){
if(!x.c||x.a==a)continue;
incl(x.a,n,d+1,v+x.b);
}
}
int findc(int n, int a, int& c, int num){
int s=0;
for(auto x:grafo[n]){
if(!x.c||x.a==a)continue;
s+=findc(x.a,n,c,num);
}
if(abs(s-num/2)<=1)c=n;
return s+1;
}
int findsize(int n, int a){
int s=0;
for(auto x:grafo[n]){
if(!x.c||x.a==a)continue;
s+=findsize(x.a,n);
}
return s+1;
}
void centroid(int n){
incl(n,-1,0,0);
for(int i=0;i<grafo[n].size();i++)grafo[n][i].c=0;
for(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i].a,-1);
for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i].a,-1,centres[i],sizes[i]);
for(int i=0;i<grafo[n].size();i++)centroid(centres[i]);
}
int best_path(int N, int K, int H[][2], int L[]){
::N=N,::K=K;
for(int i=0;i<N-1;i++){
grafo[H[i][0]].push_back({H[i][1],1,(ll)L[i]});
grafo[H[i][1]].push_back({H[i][0],1,(ll)L[i]});
}
sizes[0]=findsize(0,-1);
findc(0,-1,centres[0],sizes[0]);
centroid(centres[0]);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void centroid(int)':
race.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo[n].size();i++)grafo[n][i].c=0;
~^~~~~~~~~~~~~~~~
race.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i].a,-1);
~^~~~~~~~~~~~~~~~
race.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i].a,-1,centres[i],sizes[i]);
~^~~~~~~~~~~~~~~~
race.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grafo[n].size();i++)centroid(centres[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... |