Submission #1030689

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1030689	2024-07-22 08:36:14	vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	447 ms	42404 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>
using namespace std;
#include "railroad.h"
int rev[500100],par[500100],prf[500100];
int abp(int n){
    return par[n]?par[n]=abp(par[n]):n;
}
bool merge(int a,int b){
    a=abp(a),b=abp(b);
    if(a-b)return par[a]=b;
    return 0;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    map<int,int>mp;
    s.push_back(1e9);
    t.push_back(1);
    for(auto i:s) mp[i];
    for(auto i:t) mp[i];
    int CC=0;
    for(auto&[i,j]:mp)
        rev[j=++CC]=i;
    long long ans=0;
    for(int i=0;i<=n;i++){
        s[i]=mp[s[i]];
        t[i]=mp[t[i]];
        merge(s[i],t[i]);
        prf[s[i]]++;
        prf[t[i]]--;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railroad.cpp: In function 'bool merge(int, int)':
railroad.cpp:10:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   10 |     if(a-b)return par[a]=b;
      |                   ~~~~~~^~

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