Submission #419265

#	Time	Username	Problem	Language	Result	Execution time	Memory
419265		JeanBombeur	Roller Coaster Railroad (IOI16_railroad)	C++17	64 / 100	139 ms	16676 KiB

railroad

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36