Submission #729473

#	Time	Username	Problem	Language	Result	Execution time	Memory
729473		NemanjaSo2005	Race (IOI11_race)	C++14	21 / 100	3051 ms	19328 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[200005];
int N,K,res=1e9;
const int INF=1e9;
int kol[200005],najb[1000005],p1,p2;
ll duzina[200005],puta[200005];
bool block[200005];
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){
   return gde;
   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=kol[stablo[gde][i].gde];
   }
   if(sled==-1)
      return gde;
   return nadji(sled,gde,pola);
}
vector<int> V,W;
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);
   W.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;
      if(gde==pret)
         W.clear();
      racunaj(stablo[gde][i].gde,gde,dist+stablo[gde][i].cena,put+1);
      if(gde==pret)
         for(int i=0;i<W.size();i++)
            if(duzina[W[i]]<=K)
               najb[duzina[W[i]]]=min(najb[duzina[W[i]]],puta[W[i]]);
   }
   return;
}
void rek(int gde){
   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:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int nadji(int, int, int)':
race.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void racunaj(int, int, long long int, int)':
race.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |          for(int i=0;i<W.size();i++)
      |                      ~^~~~~~~~~
race.cpp: In function 'void rek(int)':
race.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
race.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i=0;i<stablo[c].size();i++)
      |                ~^~~~~~~~~~~~~~~~~

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