Submission #729523

#	Time	Username	Problem	Language	Result	Execution time	Memory
729523		NemanjaSo2005	Race (IOI11_race)	C++14	43 / 100	476 ms	76468 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct grana{
   int gde;
   ll cena;
}pp;
vector<grana> stablo[2000005];
bool zan;
int N,K,res=1e9;
const int INF=1e9;
int kol[2000005],najb[10000005],p1,p2;
ll duzina[2000005],puta[2000005];
bool block[2000005];
ll min(int a,ll b){
   if(a<b)
      return a;
   return b;
}
int rootuj(int gde,int pret){
   if(block[gde])
      return 0;
   kol[gde]=1;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i].gde!=pret)
         kol[gde]+=rootuj(stablo[gde][i].gde,gde);
   return kol[gde];
}
int nadji(int gde,int pret,int pola){
   //if(zan)
    //  cout<<gde<<" "<<pret<<endl;
   int sled=-1;
   for(int 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<int> V;
void racunaj(int gde,int pret,ll dist,int 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(int 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(int gde){
  // cout<<"REK NA "<<gde<<endl;
  // zan=(gde==19);
   rootuj(gde,gde);
   int c=nadji(gde,gde,kol[gde]/2+3);
   V.clear();
   racunaj(c,c,0,0);

  // cout<<"CENTROID JE "<<c<<endl;
  /* for(int i=0;i<V.size();i++)
      cout<<V[i]<<": "<<puta[V[i]]<<" "<<duzina[V[i]]<<endl;
   cout<<endl;
   cout<<"RES= "<<res<<endl;
*/
   for(int i=0;i<V.size();i++){
      if(duzina[V[i]]>K)
         continue;
      najb[duzina[V[i]]]=INF;
   }
   block[c]=true;
   kol[c]=INF;
   for(int 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(int 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(int i=0;i<=K;i++)
      najb[i]=INF;
   rek(1);
   if(res==1e9)
      return -1;
   return res;
}

Compilation message (stderr)

race.cpp: In function 'int rootuj(int, int)':
race.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int nadji(int, int, int)':
race.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void racunaj(int, int, long long int, int)':
race.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void rek(int)':
race.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
race.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int i=0;i<stablo[c].size();i++)
      |                ~^~~~~~~~~~~~~~~~~

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