제출 #419265

#제출 시각아이디문제언어결과실행 시간메모리
419265JeanBombeurRoller Coaster Railroad (IOI16_railroad)C++17
64 / 100
139 ms16676 KiB
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include "railroad.h" using namespace std; // <|°_°|> const int INFINI = (1000 * 1000 * 1000); const int MAX_COORD = (400 * 1000 + 2); int Dsu[MAX_COORD]; pair <int, int> Evenements[MAX_COORD]; int Sommes[MAX_COORD]; int Correspondances[MAX_COORD]; pair <int, int> Aretes[MAX_COORD]; int nbAretes = 0; long long coutTotal = 0; int nbSections; int Find(int a) { if (Dsu[a] < 0) return a; return Dsu[a] = Find(Dsu[a]); } void Union(int a, int b) { int rA = Find(a), rB = Find(b); if (rA == rB) return; if (Dsu[rA] > Dsu[rB]) swap(rA, rB); Dsu[rA] += Dsu[rB]; Dsu[rB] = rA; return; } long long plan_roller_coaster(vector<int> Entrees, vector<int> Sorties) { Entrees.push_back(INFINI); Sorties.push_back(1); nbSections = Entrees.size(); for (int i = 0; i < nbSections; i ++) { Evenements[2 * i] = {Entrees[i], i + 1}; Evenements[2 * i + 1] = {Sorties[i], - (i + 1)}; } sort(Evenements, Evenements + 2 * nbSections); int nbDiff = 0; for (int i = 0; i < 2 * nbSections; i ++) { int dep = i; while (i < 2 * nbSections && Evenements[i].first == Evenements[i + 1].first) i ++; for (int j = dep; j <= i; j ++) { int id = Evenements[j].second; if (id > 0) { Entrees[id - 1] = nbDiff; Sommes[nbDiff] ++; } else { Sorties[- id - 1] = nbDiff; Sommes[nbDiff] --; } } Correspondances[nbDiff ++] = Evenements[i].first; } for (int i = 0; i < nbDiff; i ++) { Dsu[i] = -1; } for (int i = 0; i < nbSections; i ++) { Union(Entrees[i], Sorties[i]); } int nbOuverts = 0; for (int i = 0; i < nbDiff - 1; i ++) { nbOuverts += Sommes[i]; coutTotal += max(0, nbOuverts) * (Correspondances[i + 1] - Correspondances[i]); if (nbOuverts != 0) { Union(i, i + 1); } else if (Find(i) != Find(i + 1)) { Aretes[nbAretes ++] = {Correspondances[i + 1] - Correspondances[i], i}; } } sort(Aretes, Aretes + nbAretes); for (int i = 0; i < nbAretes; i ++) { int id = Aretes[i].second; if (Find(id) != Find(id + 1)) { coutTotal += Correspondances[id + 1] - Correspondances[id]; Union(id, id + 1); } } return coutTotal; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...