제출 #110238

#제출 시각아이디문제언어결과실행 시간메모리
110238Arturgo경주 (Race) (IOI11_race)C++14
9 / 100
288 ms55552 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...