Submission #205350

#	Time	Username	Problem	Language	Result	Execution time	Memory
205350		combi1k1	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	264 ms	18388 KiB

railroad

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 4e5 + 5;

typedef pair<int,int>   ii;
typedef pair<int,ii>    ed;

int p[N];
int s[N];

int init(int n) {
    iota(p,p + n,0);
    fill(s,s + n,1);
    return  1;
}
int lead(int x) {
    return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y)   {
    x = lead(x);
    y = lead(y);

    if (x == y) return  0;
    if (s[x] < s[y])
        swap(x,y);
    p[y] = x;
    s[x] += s[y];

    return  1;
}

int f[N];

ll  plan_roller_coaster(vector<int> s,vector<int> t)    {
    s.pb(1e9);
    t.pb(1);

    int n = s.size();

    vector<int> val;

    for(int i = 0 ; i < n ; ++i)    {
        val.pb(s[i]);
        val.pb(t[i]);
    }

    sort(all(val));
    val.erase(unique(all(val)),val.end());

    init(sz(val));

    for(int i = 0 ; i < n ; ++i)    {
        int l = lower_bound(all(val),s[i]) - val.begin();
        int r = lower_bound(all(val),t[i]) - val.begin();

        f[l]++;
        f[r]--;

        join(l,r);
    }
    ll  ans = 0;
    ll  Sum = 0;

    vector<ed>  E;

    for(int i = 1 ; i < sz(val) ; ++i)  {
        Sum += f[i - 1];

        if (Sum == 0)    E.pb(val[i] - val[i - 1],ii(i - 1,i));
        else    {
            join(i - 1,i);

            if (Sum > 0)
                ans += Sum * (val[i] - val[i - 1]);
        }
    }
    sort(all(E));

    for(ed  e : E)  {
        int w = e.X;
        int u = e.Y.X;
        int v = e.Y.Y;

        if (join(u,v))
            ans += w;
    }
    return  ans;
}

//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    cout << plan_roller_coaster({1,4,5,6},{7,3,8,6}) << endl;
//}

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