Submission #898139

#	Time	Username	Problem	Language	Result	Execution time	Memory
898139		ThylOne	Race (IOI11_race)	C++14	9 / 100	2340 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;
int ANS = maxiN*2;
vector<pair<int,int>>  solve(int node,int W=0){
  //1 - trouver la centroid
  vector<int> nodes;
  map<int,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<map<int,int>> maps;
  for(auto e:links[centroid])if(!blocked[e.first]){
    map<int,int> val;
    vector<pair<int,int>> re = solve(e.fils,e.weight);
    for(auto r:re){
      //On stock le meilleur repréentant pour chaque valeur
      if(val.count(r.first)){
        val[r.first] = min(val[r.first],r.second);
      }else{
        val[r.first] = r.second;
      }
    }
    maps.push_back(val);
  }
  set<pair<int,int>> SET;
  for(int i = 0;i<maps.size();i++){
    for(auto key:maps[i])
      SET.insert(key);
  }
  //3 Conquer
  SET.insert({0,0});
  vector<pair<int,int>> returnPairs;
  for(int i = 0;i<maps.size();i++){
    for(auto key:maps[i])
      SET.erase(key);
    for(auto key:maps[i]){
      if(target>=key.first+W)
        returnPairs.push_back({key.first+W,key.second+1});
      pair<int,int> p ={target-key.first,0};
      auto it = SET.lower_bound(p);
      if(it!=SET.end() && it->first==target-key.first){
        ANS = min(ANS, it->second+key.second);
      }
    }
      
    for(auto key:maps[i])
      SET.insert(key);
  }

  //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<int, int> > solve(int, int)':
race.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::map<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i = 0;i<maps.size();i++){
      |                 ~^~~~~~~~~~~~
race.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::map<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 0;i<maps.size();i++){
      |                 ~^~~~~~~~~~~~

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