Submission #270649

#	Time	Username	Problem	Language	Result	Execution time	Memory
270649		stoyan_malinin	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1054 ms	48220 KiB

railroad

#include "railroad.h"
//#include "grader.cpp"

#include <set>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const long long inf = 1e18 + 5;

struct DSU
{
    vector <int> parent;

    DSU(){}
    DSU(int n)
    {
        this->parent.resize(n+5);
        for(int i = 0;i<=n;i++) this->parent[i] = i;
    }

    int Find(int x)
    {
        if(parent[x]==x) return x;

        parent[x] = Find(parent[x]);
        return parent[x];
    }

    bool Union(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return false;

        parent[v] = u;
        return true;
    }
};

int n;
vector <int> s, t;

map <int, int> numCode;
vector <int> invCode;

void init()
{
    set <int> nums;
    for(int x: s) nums.insert(x);
    for(int x: t) nums.insert(x);

    int ind = 0;
    invCode.resize(nums.size()+5);

    for(int x: nums)
    {
        numCode[x] = ind;
        invCode[ind] = x;

        ind++;
        //cout << x << " -> " << code[x] << '\n';
    }

    for(int &x: s) x = numCode[x];
    for(int &x: t) x = numCode[x];
}

long long plan_roller_coaster(vector<int> _s, vector<int> _t)
{
    _s.push_back(int(1e9+5));
    _t.push_back(1);

    s = _s;
    t = _t;
    n = s.size();
    init();

    DSU T = DSU(2*n+5);
    long long answer = 0;

    vector <int> start, finish;
    finish.assign(numCode.size()+5, 0);
    start.assign(numCode.size()+5, 0);

    //cout << '\n';

    for(int i = 0;i<n;i++)
    {
        //cout << s[i] << " " << t[i] << '\n';
        T.Union(s[i], t[i]);

        int x = s[i];
        int y = t[i];
        if(x>y) swap(x, y);

        start[x] += ((s[i]<t[i])?+1:-1);
        finish[y] += ((s[i]<t[i])?+1:-1);
    }

    int val = 0;
    for(int i = 0;i<numCode.size()-1;i++)
    {
        val += start[i];
        val -= finish[i];

        //cout << i << " => " << val << " || " << start[i] << " " << finish[i] << '\n';
        if(val>0)
        {
            T.Union(i, i+1);
            answer += val*1LL*(invCode[i+1]-invCode[i]);
        }
        else if(val<0)
        {
            T.Union(i, i+1);
        }
    }

    vector <pair <long long, int>> edges;
    for(int i = 0;i<numCode.size()-1;i++)
    {
        if(T.Find(i)!=T.Find(i+1))
        {
            //cout << " -> " << i << '\n';
            edges.push_back({invCode[i+1]-invCode[i], i});
        }
    }

    sort(edges.begin(), edges.end());
    for(pair <long long, int> x: edges)
    {
        if(T.Union(x.second, x.second+1)==true) answer += x.first;
    }

    return answer;
}
/*
2
4 2
3 5

4
1 7
4 3
5 8
6 6
*/

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0;i<numCode.size()-1;i++)
      |                   ~^~~~~~~~~~~~~~~~~
railroad.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0;i<numCode.size()-1;i++)
      |                   ~^~~~~~~~~~~~~~~~~

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