이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct grana{
ll gde;
ll cena;
}pp;
vector<grana> stablo[200005];
bool zan;
ll N,K,res=1e9;
const ll INF=1e9;
ll kol[200005],najb[1000005],p1,p2;
ll duzina[200005],puta[200005];
bool block[200005];
ll rootuj(ll gde,ll pret){
if(block[gde])
return 0;
kol[gde]=1;
for(ll i=0;i<stablo[gde].size();i++)
if(stablo[gde][i].gde!=pret)
kol[gde]+=rootuj(stablo[gde][i].gde,gde);
return kol[gde];
}
ll nadji(ll gde,ll pret,ll pola){
//if(zan)
// cout<<gde<<" "<<pret<<endl;
ll sled=-1;
for(ll i=0;i<stablo[gde].size();i++){
if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret)
continue;
if(kol[stablo[gde][i].gde]>pola)
sled=stablo[gde][i].gde;
}
if(sled==-1)
return gde;
return nadji(sled,gde,pola);
}
vector<ll> V;
void racunaj(ll gde,ll pret,ll dist,ll put){
duzina[gde]=dist;
puta[gde]=put;
// cout<<"DFS "<<gde<<" "<<pret<<" "<<put<<" "<<dist<<endl;
if(dist<=K)
res=min(res,put+najb[K-dist]);
if(dist==K)
res=min(res,put);
V.push_back(gde);
for(ll i=0;i<stablo[gde].size();i++){
if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret)
continue;
racunaj(stablo[gde][i].gde,gde,dist+stablo[gde][i].cena,put+1);
}
if(dist<=K)
najb[dist]=min(najb[dist],put);
return;
}
void rek(ll gde){
// cout<<"REK NA "<<gde<<endl;
// zan=(gde==19);
rootuj(gde,gde);
ll c=nadji(gde,gde,kol[gde]/2+3);
V.clear();
racunaj(c,c,0,0);
// cout<<"CENTROID JE "<<c<<endl;
/* for(ll i=0;i<V.size();i++)
cout<<V[i]<<": "<<puta[V[i]]<<" "<<duzina[V[i]]<<endl;
cout<<endl;
cout<<"RES= "<<res<<endl;
*/
for(ll i=0;i<V.size();i++){
if(duzina[V[i]]>K)
continue;
najb[duzina[V[i]]]=INF;
}
block[c]=true;
kol[c]=INF;
for(ll i=0;i<stablo[c].size();i++)
if(!block[stablo[c][i].gde])
rek(stablo[c][i].gde);
return;
}
int best_path(int n,int k,int h[][2],int l[]){
N=n;
K=k;
for(ll i=0;i<N-1;i++){
h[i][0]++;
h[i][1]++;
pp.cena=l[i];
pp.gde=h[i][1];
stablo[h[i][0]].push_back(pp);
//cout<<h[i][0]<<" "<<h[i][1]<<endl;
pp.gde=h[i][0];
stablo[h[i][1]].push_back(pp);
}
for(ll i=0;i<=K;i++)
najb[i]=INF;
rek(1);
if(res==1e9)
return -1;
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'long long int rootuj(long long int, long long int)':
race.cpp:20:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(ll i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'long long int nadji(long long int, long long int, long long int)':
race.cpp:29:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(ll i=0;i<stablo[gde].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void racunaj(long long int, long long int, long long int, long long int)':
race.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(ll i=0;i<stablo[gde].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void rek(long long int)':
race.cpp:72:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(ll i=0;i<V.size();i++){
| ~^~~~~~~~~
race.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(ll i=0;i<stablo[c].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... |