Submission #289475

#	Time	Username	Problem	Language	Result	Execution time	Memory
289475		Kastanda	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	380 ms	19976 KiB

railroad

// M
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
const int N = 200005 * 2;
int n, P[N], S[N], T[N];
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline bool Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return 0;
        P[v] = u;
        return 1;
}

long long plan_roller_coaster(vector < int > _S, vector < int > _T)
{
        memset(P, -1, sizeof(P));
        n = (int)_S.size();
        for (int i = 0; i < n; i ++)
                S[i] = _S[i], T[i] = _T[i];
        S[n] = (int)(1e9 + 9); T[n] = 1;

        vector < int > U;
        for (int i = 0; i <= n; i ++)
        {
                U.push_back(S[i]);
                U.push_back(T[i]);
        }
        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        vector < pair < int , int > > A;
        for (int i = 0; i <= n; i ++)
        {
                S[i] = (int)(lower_bound(U.begin(), U.end(), S[i]) - U.begin());
                T[i] = (int)(lower_bound(U.begin(), U.end(), T[i]) - U.begin());
                A.push_back({S[i], 1});
                A.push_back({T[i], -1});
                Merge(S[i], T[i]);
        }
        sort(A.begin(), A.end());
        ll Cur = 0, tot = 0;
        for (int i = 0; i + 1 < (int)A.size(); i ++)
        {
                Cur += A[i].second;
                if (Cur > 0)
                        tot += Cur * (U[A[i + 1].first] - U[A[i].first]);
                if (Cur)
                        Merge(A[i].first, A[i + 1].first);
        }
        vector < int > R((int)A.size() - 1);
        iota(R.begin(), R.end(), 0);
        sort(R.begin(), R.end(), [&](int i, int j){return U[A[i + 1].first] - U[A[i].first] < U[A[j + 1].first] - U[A[j].first];});
        for (int i : R)
                if (Merge(A[i].first, A[i + 1].first))
                        tot += U[A[i + 1].first] - U[A[i].first];
        return tot;
}

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