Submission #898114

#	Time	Username	Problem	Language	Result	Execution time	Memory
898114		ThylOne	Race (IOI11_race)	C++14	0 / 100	2 ms	8796 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
  map<int,int> sub_tree;
  vector<int> nodes;
  map<int,vector<int>> subsub;
  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_);
      subsub[node_].push_back(re);
      sub_tree[node_]+=re;
    }
    sub_tree[node_]++;
    return sub_tree[node_];
  };
  dfs(node,-1);
  int miniDiff = maxiN+42;
  int centroid = nodes[0];
  for(int nc:nodes){
    bool ok;
    int maxiDist=0;
    int sizeC = nodes.size();
    int maxSub = sizeC/2;
    for(int d:subsub[nc]){
      maxiDist=max(maxiDist,(d<maxSub?0:abs(maxSub-d)));
    }
    if(nc!=node){
      int rest = sizeC-sub_tree[nc];
      maxiDist=max(maxiDist,(rest<maxSub?0:abs(maxSub-rest)));
    }  
    if(miniDiff>maxiDist){
      miniDiff=maxiDist;
      centroid=nc;
    }
  }
  blocked[centroid]=true;
  //2 Divide
  map<int,int> val;
  vector<int> mid;
  for(auto e:links[centroid])if(!blocked[e.first]){
    vector<pair<int,int>> re = solve(e.fils,e.weight);
    for(auto r:re){
      if(r.first == target/2 && target%2==0)mid.push_back(r.second);
      //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;
      }
    }
  }
  //3 Conquer
  // On regarde si on a pas trouvé un chemin
  sort(mid.begin(),mid.end());
  if(mid.size()>1){
    ANS = min(ANS,mid[0]+mid[1]);
  }
  //On en profite pour remplir le vecteur de fin
  vector<pair<int,int>> returnPairs;
  for(auto key:val){
    returnPairs.push_back({key.first+W,key.second+1});
    if(key.first==target){
      ANS = min(ANS,key.second);
    }else if(val.count(target-key.first)){
      ANS = min(ANS,(int)(key.second+val[target-key.first]));
    }
  }

  //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:34:10: warning: unused variable 'ok' [-Wunused-variable]
   34 |     bool ok;
      |          ^~

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