Submission #332156

#	Time	Username	Problem	Language	Result	Execution time	Memory
332156		ruatin	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	220 ms	17628 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define all(a) a.begin(),a.end()
#define lli long long
using namespace std;

const int N = 4e5+5;
int n;
int in[N], out[N];
lli that[N], res;

struct DSU
{
    int n;
    vector<int> id;
    DSU(int n) : n(n), id(n+1,-1) {}
    int root(int u)
    {
        return id[u]<0 ? u : id[u]=root(id[u]);
    }
    bool join(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return 0;
        if(id[u]>id[v])
            swap(u,v);
        id[u] += id[v];
        id[v] = u;
        return 1;
    }
};

struct edge
{
    int u, v, c;
};
vector<edge> E;

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
  	n = s.size();
    vector<int> rrh;
    forinc(i,0,n-1)
    {
        rrh.push_back(s[i]);
        rrh.push_back(t[i]);
    }
    sort(all(rrh));
    rrh.erase(unique(all(rrh)),rrh.end());
    int ma = rrh.size();
    DSU dsu(ma);
    forinc(i,0,n-1)
    {
        int _s = lower_bound(all(rrh),s[i]) - rrh.begin() + 1;
        int _t = lower_bound(all(rrh),t[i]) - rrh.begin() + 1;
        that[_s] = s[i], that[_t] = t[i];
        out[_s]++;
        in[_t]++;
        dsu.join(_s,_t);
    }
    out[ma]++;
    in[1]++;
    fordec(i,ma,1)
    {
        if(in[i] > out[i])
        {
            in[i-1] += in[i]-out[i];
            res += 1ll*(in[i]-out[i])*(that[i]-that[i-1]);
            dsu.join(i-1,i);
        }
        else if(in[i] < out[i])
        {
            out[i-1] += out[i] - in[i];
            dsu.join(i-1,i);
        }
    }
    forinc(i,1,ma-1) if(dsu.root(i) != dsu.root(i+1))
        E.push_back({i,i+1,that[i+1]-that[i]});
    sort(all(E),[](const edge &a, const edge &b)
    {
        return a.c < b.c;
    });
    for(edge e:E)
    {
        if(dsu.join(e.u, e.v))
            res += e.c;
    }
    return res;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:80:37: warning: narrowing conversion of '(that[(i + 1)] - that[i])' from 'long long int' to 'int' [-Wnarrowing]
   80 |         E.push_back({i,i+1,that[i+1]-that[i]});
      |                            ~~~~~~~~~^~~~~~~~

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