Submission #618120

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
618120	2022-08-01 23:33:51	Bench0310	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	614 ms	40100 KiB

railroad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
typedef long long ll;
ll plan_roller_coaster(vector<int> s,vector<int> t)
{
    s.push_back(1<<30);
    t.push_back(1);
    int n=s.size();
    map<int,int> h;
    vector<int> x;
    for(int y:s) x.push_back(y);
    for(int y:t) x.push_back(y);
    sort(x.begin(),x.end());
    x.erase(unique(x.begin(),x.end()),x.end());
    int m=x.size();
    for(int i=0;i<m;i++) h[x[i]]=i;
    vector<int> d(m,0);
    vector<int> p(m,0);
    for(int i=0;i<m;i++) p[i]=i;
    vector<int> sz(m,1);
    function<int(int)> find_set=[&](int a)->int
    {
        if(a==p[a]) return a;
        else return p[a]=find_set(p[a]);
    };
    auto merge_sets=[&](int a,int b)->int
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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