이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define DB printf("debug\n");
using namespace std;
int n,k,ans=INT_MAX;
vector < pair < int , int > > ed[200005];
vector < bool > cenbef(200005,0);
vector < int > subcnt(200005,0);
int sub_count(int vn,int vb){//kendisi dahil
subcnt[vn]=1;
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
if(!cenbef[vnx]&&vnx!=vb){
subcnt[vn]+=sub_count(vnx,vn);
}
}
return subcnt[vn];
}
int find_cen(int vn,int vb,int ts){
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
if(!cenbef[vnx]&&vnx!=vb&&subcnt[vnx]>ts/2)
return find_cen(vnx,vn,ts);
}
return vn;
}
void merge(map<int,int>&allm,map<int,int>&sbtm){
map<int,int>::iterator it;
for(it=sbtm.begin();it!=sbtm.end();it++){
if(allm.find(k-it->st)!=allm.end()){
ans=min(ans,allm[k-it->st]+it->nd);
}
}
for(it=sbtm.begin();it!=sbtm.end();it++){
if(allm.find(it->st)==allm.end()){
allm[it->st]=it->nd;
}
else{
allm[it->st]=min(allm[it->st],it->nd);
}
}
}
void dfs(int vn,int vb,int rn,int wn,map<int,int>&sbtm){
if(wn>k)return;
if(sbtm.find(wn)==sbtm.end())sbtm[wn]=rn;
else sbtm[wn]=min(sbtm[wn],rn);
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st,edw=ed[vn][i].nd;
if(!cenbef[vnx]&&vnx!=vb)
dfs(vnx,vn,rn+1,wn+edw,sbtm);
}
}
void rou_find(int vn){
map < int , int > allm;
allm[0]=0;
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
int edl=ed[vn][i].nd;
if(!cenbef[vnx]){
map < int , int > sbtm;
dfs(vnx,vn,1,edl,sbtm);
merge(allm,sbtm);
}
}
}
void solve(int vn){
sub_count(vn,-1);
int cen=find_cen(vn,-1,subcnt[vn]);
cenbef[cen]=1;
rou_find(cen);
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
if(!cenbef[vnx])
rou_find(vnx);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;k=K;
for(int i=0;i<N-1;i++){
ed[H[i][0]].push_back(make_pair(H[i][1],L[i]));
ed[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
solve(0);
if(ans==INT_MAX)
return -1;
else return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'int sub_count(int, int)':
race.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void rou_find(int)':
race.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].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... |