Submission #727734

#	Time	Username	Problem	Language	Result	Execution time	Memory
727734		NemanjaSo2005	Race (IOI11_race)	C++14	0 / 100	3 ms	5060 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){
   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;
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);
   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);
   }
   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;*/
   p1=INF;
   p2=INF;
   for(int i=0;i<V.size();i++){
      if(duzina[V[i]]>K)
         continue;
      if(duzina[V[i]]==K/2){
         if(puta[V[i]]<p1){
            p2=p1;
            p1=puta[V[i]];
         }
         else
            p2=min(p2,puta[V[i]]);
      }
      else
         najb[duzina[V[i]]]=min(najb[duzina[V[i]]],puta[V[i]]);
   }
   res=min(res,p1+p2);
   for(int i=0;i<V.size();i++)
      if(duzina[V[i]]!=K/2 and duzina[V[i]]<=K)
         res=min(res,najb[duzina[V[i]]]+najb[K-duzina[V[i]]]);
   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:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void racunaj(int, int, long long int, int)':
race.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void rek(int)':
race.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
race.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for(int i=0;i<V.size();i++)
      |                ~^~~~~~~~~
race.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
race.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i=0;i<stablo[c].size();i++)
      |                ~^~~~~~~~~~~~~~~~~

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