제출 #729530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729530		NemanjaSo2005	Race (IOI11_race)	C++14	43 / 100	469 ms	36168 KiB

race

#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++)
      |               ~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57