Submission #110238

#	Time	Username	Problem	Language	Result	Execution time	Memory
110238		Arturgo	Race (IOI11_race)	C++14	9 / 100	288 ms	55552 KiB

race

#include "race.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;

int INFINI = 1000 * 1000 * 1000;

int nbVilles, tailleTotale;
vector<pair<int, int>> voisins[200 * 1000];

struct Retour {
  long long decProf;
  int decChemin;
  map<long long, int> profs;

  Retour() {
    decChemin = 0;
    decProf = 0;
    profs[0] = 0;
  }

  void shift(long long taille) {
    decChemin++;
    decProf += taille;
  }

  int getChemin(long long prof) {
    if(profs.find(prof - decProf) == profs.end())
      return INFINI;
    return profs[prof - decProf] + decChemin;
  }

  void setChemin(long long prof, int chemin) {
    profs[prof - decProf] = chemin - decChemin;
  }

  vector<pair<long long, int>> getProfs() {
    vector<pair<long long, int>> res;
    for(pair<long long, int> paire : profs) {
      res.push_back({paire.first + decProf, paire.second + decChemin});
    }
    return res;
  }
};

vector<Retour> retours;

int melChemin = INFINI;

int fusion(int a, int b) {
  Retour& retA = retours[a];
  Retour& retB = retours[b];
  
  if(retA.profs.size() > retB.profs.size())
    fusion(b, a);

  vector<pair<long long, int>> profsA = retA.getProfs();
  for(pair<long long, int> paire : profsA) {
    melChemin = min(melChemin, paire.second + retB.getChemin(tailleTotale - paire.first));
  }

  for(pair<long long, int> paire : profsA) {
    retB.setChemin(paire.first, min(retB.getChemin(paire.first), paire.second));
  }

  return b;
}

int calcChemin(int noeud, int parent = -1) {
  int id = retours.size();
  retours.push_back(Retour());

  for(pair<int, int> voisin : voisins[noeud]) {
    if(voisin.first == parent)
      continue;
    int retour = calcChemin(voisin.first, noeud);
    retours[retour].shift(voisin.second);

    id = fusion(id, retour);
  }

  return id;
}

int best_path(int _nbVilles, int _tailleTotale, int adjs[][2], int tailles[]) {
  nbVilles = _nbVilles;
  tailleTotale = _tailleTotale;

  for(int iRoute = 0;iRoute < nbVilles - 1;iRoute++) {
    voisins[adjs[iRoute][0]].push_back({adjs[iRoute][1], tailles[iRoute]});
    voisins[adjs[iRoute][1]].push_back({adjs[iRoute][0], tailles[iRoute]});
  }

  calcChemin(0);

  if(melChemin == INFINI)
    return -1;
  return melChemin;
}

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