Submission #906809

#	Time	Username	Problem	Language	Result	Execution time	Memory
906809		mathnetic	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	543 ms	29584 KiB

railroad

#include <bits/stdc++.h>

#include "railroad.h"



using namespace std;



typedef pair<int, int> P;

typedef long long L;



unordered_map<int, int> m;



int f(int x) {

    if (m[x] == 0) m[x] = x;

    return (x == m[x]) ? x : (m[x] = f(m[x]));

}



void u(int x, int y) {

    m[f(x)] = f(y);

}



bool c(P a, P b) {

    return (a.second - a.first) < (b.second - b.first);

}



L plan_roller_coaster(vector<int> s, vector<int> t) {

    L r = 0;

    s.push_back(1e9);

    t.push_back(1);

    int n = s.size();

    vector<P> v, d;



    for (int i = 0; i < n; ++i) {

        u(s[i], t[i]);

        v.emplace_back(s[i], 1);

        v.emplace_back(t[i], -1);

    }



    sort(v.begin(), v.end());

    int b = 0;



    for (int i = 0, j = 0; i < v.size(); i = j) {

        for (; j < v.size() && v[j].first == v[i].first; ++j) {

            b += v[j].second;

        }



        if (!(j >= v.size())) {

            if (b > 0) {

                r += static_cast<L>(b) * (v[j].first - v[i].first);

            }



            if (b == 0) {

                d.emplace_back(v[i].first, v[j].first);

            } else {

                u(v[j].first, v[i].first);

            }

        }

    }



    sort(d.begin(), d.end(), c);



    for (auto i : d) {

        if (f(i.first) != f(i.second)) {

            r += i.second - i.first;

            u(i.first, i.second);

        }

    }



    return r;

}

Compilation message (stderr)

railroad.cpp: In function 'L plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:79:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0, j = 0; i < v.size(); i = j) {
      |                            ~~^~~~~~~~~~
railroad.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (; j < v.size() && v[j].first == v[i].first; ++j) {
      |                ~~^~~~~~~~~~
railroad.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (!(j >= v.size())) {
      |               ~~^~~~~~~~~~~

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