Submission #289463

#	Time	Username	Problem	Language	Result	Execution time	Memory
289463		Kastanda	Roller Coaster Railroad (IOI16_railroad)	C++11	34 / 100	2045 ms	27584 KiB

railroad

// M
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
int n;
map < int , int > P;
int Find(int v)
{
        return (!P[v] ? 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)
{
        n = (int)S.size();
        vector < pair < int , int > > A;
        for (int i = 0; i < n; i ++)
        {
                A.push_back({S[i], 1});
                A.push_back({T[i], -1});
                Merge(S[i], T[i]);
        }
        A.push_back({(int)(1e9 + 9), 1});
        A.push_back({1, -1});
        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 * (A[i + 1].first - 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 A[i + 1].first - A[i].first < A[j + 1].first - A[j].first;});
        for (int i : R)
                if (Merge(A[i].first, A[i + 1].first))
                        tot += A[i + 1].first - A[i].first;
        return tot;
}

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