Submission #427963

#	Time	Username	Problem	Language	Result	Execution time	Memory
427963		chirathnirodha	Race (IOI11_race)	C++17	43 / 100	3061 ms	122128 KiB

race

//Coded by Chirath Nirodha
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define P push
typedef long long ll;
 
vector<pair<int,int> > adj[1000000];
vector<pair<int,int> > preadj[1000000];
int ans=10000010;
int kk;
int siz[1000000];
void preproc(int x,int y){
  siz[y]=1;
  vector<pair<int,int> > v;
  for(int i=0;i<preadj[y].size();i++){
    int to=preadj[y][i].F;
    ll len=preadj[y][i].S;
    if(to==x)continue;
    preproc(y,to);
    siz[y]+=siz[to];
    v.PB(MP(siz[to],i));
  }
  sort(v.rbegin(),v.rend());
  for(int i=0;i<v.size();i++)adj[y].PB(MP(preadj[y][v[i].S].F,preadj[y][v[i].S].S));
}
map<int,int> dfs(int x,int y){
  map<int,int> mpy;
  mpy[0]=0;
  for(int i=0;i<adj[y].size();i++){
    int to=adj[y][i].F;
    int len=adj[y][i].S;
    if(to==x)continue;
    map<int,int> mpto=dfs(y,to);
    if(i==0){
      if(mpto.count(kk-len)!=0)ans=min(ans,mpto[kk-len]+1);
      for(auto itr=mpto.begin();itr!=mpto.end();itr++){
         pair<int,int> p=*itr;
         if(p.F+len>kk)break;
         if(mpy.count(p.F+len)==0)mpy[p.F+len]=p.S+1;
         else mpy[p.F+len]=min(mpy[p.F+len],p.S+1);
      }
    }
    else{
      for(auto itr=mpto.begin();itr!=mpto.end();itr++){
         pair<int,int> p=*itr;
         if(p.F+len>kk)break;
         if(mpy.count(kk-(p.F+len))!=0)ans=min(ans,p.S+1+mpy[kk-(p.F+len)]);
      }
      for(auto itr=mpto.begin();itr!=mpto.end();itr++){
         pair<int,int> p=*itr;
         if(p.F+len>kk)break;
         if(mpy.count(p.F+len)==0)mpy[p.F+len]=p.S+1;
         else mpy[p.F+len]=min(mpy[p.F+len],p.S+1);
      }
    }
  }
  return mpy;
}
int best_path(int n, int K, int h[][2], int l[]){
    kk=K;
    for(int i=0;i<n-1;i++){
      preadj[h[i][0]].PB(MP(h[i][1],l[i]));
      preadj[h[i][1]].PB(MP(h[i][0],l[i]));
    }
    preproc(0,0);
    dfs(0,0);
    if(ans>=n)return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void preproc(int, int)':
race.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i=0;i<preadj[y].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
race.cpp:22:8: warning: unused variable 'len' [-Wunused-variable]
   22 |     ll len=preadj[y][i].S;
      |        ^~~
race.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<v.size();i++)adj[y].PB(MP(preadj[y][v[i].S].F,preadj[y][v[i].S].S));
      |               ~^~~~~~~~~
race.cpp: In function 'std::map<int, int> dfs(int, int)':
race.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<adj[y].size();i++){
      |               ~^~~~~~~~~~~~~~

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