Submission #898212

#	Time	Username	Problem	Language	Result	Execution time	Memory
898212		ThylOne	Race (IOI11_race)	C++14	9 / 100	1694 ms	262144 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxiN = 200000;
#define edge pair<int,int>
#define fils first
#define weight second

vector<edge> links[maxiN];
vector<bool> blocked;
int nbNode;
int target;
long long ANS = maxiN*2;

vector<pair<long long,long long>>  solve(int node,int W=0){
  //1 - trouver la centroid
  vector<long long> nodes;
  map<long long,int> deg;
  std::function<int(int, int)> dfs = [&](int node_,int papa=-1){
    if(blocked[node_])return 0;
    nodes.push_back(node_);
    for(auto e:links[node_])if(papa!=e.fils){
      int re = dfs(e.fils,node_);
      deg[node_]+=re;
    }
    
    return 1;
  };
  dfs(node,-1);
  int centroid=node;
  int maxiDeg = deg[node];
  for(int node_:nodes){
    if(maxiDeg<deg[node_]){
      deg[node_]=maxiDeg;
      centroid=node_;
    }
  }
  blocked[centroid]=true;
  
  //2 Divide
  vector<vector<pair<long long,long long>>> maps;
  for(auto e:links[centroid])if(!blocked[e.first]){
    vector<pair<long long,long long>> re = solve(e.fils,e.weight);
    maps.push_back(re);
  }

  map<long long,long long> VAL;
  VAL[0]=0;
  vector<pair<long long,long long>> returnPairs;
  for(int i = 0;i<maps.size();i++){

    for(auto key:maps[i]){
      if(VAL.count(target-key.first)){
        ANS = min(ANS,key.second+VAL[target-key.first]);
      }
      
      returnPairs.push_back({key.first+W,key.second+1});
    }
    //ajouter la valeur dans la map
    for(auto key:maps[i]){
      if(VAL.count(key.first)){
        VAL[key.first] = min(VAL[key.first],key.second);
      }else{
        VAL[key.first] = key.second;
      }
    }
  }
  //3 Conquer

  //On en profite pour remplir le vecteur de fin
  
  
  //cout<<centroid<<' '<<ANS<<endl; 
  //On oublit pas la ptit nouvelle
  
  returnPairs.push_back({W,1});
  return returnPairs;
}
int best_path(int N, int K, int H[][2], int L[])
{
  target=K;
  nbNode=N;
  
  blocked.resize(N,false);
  fill(blocked.begin(),blocked.end(),false);
  for(int i = 0;i<N-1;i++){
    links[H[i][0]].push_back({H[i][1],L[i]});
    links[H[i][1]].push_back({H[i][0],L[i]});
  }
  
  solve(0);
  
  return (ANS==2*maxiN?-1:ANS);
}

Compilation message (stderr)

race.cpp: In function 'std::vector<std::pair<long long int, long long int> > solve(int, int)':
race.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0;i<maps.size();i++){
      |                 ~^~~~~~~~~~~~

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