Submission #1136972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136972		the_coding_pooh	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	217 ms	15808 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

#define uwu return
#define ALL(x) x.begin(), x.end()

#define fs first
#define sc second

vector <int> discrete;

const int SIZE = 4e5 + 5;

int direct[SIZE], dsu[SIZE];

int get_id(int i){
	return lower_bound(ALL(discrete), i) - discrete.begin();
}

long long dist(int a, int b){
	if(a > b) swap(a, b);
	return discrete[b] - discrete[a];
}

int pa(int a){
	if(dsu[a] < 0)
		return a;
	return dsu[a] = pa(dsu[a]);
}

bool merge(int a, int b){
	assert(a >= 0);
	assert(b >= 0);
	a = pa(a), b = pa(b);
	if(a == b)
		return 0;
	if(dsu[a] < dsu[b])
		swap(a, b);
	dsu[b] += dsu[a];
	dsu[a] = b;
	return 1;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size() + 1;
	int mx = 0;
	for(auto i:s){
		discrete.push_back(i);
		mx = max(mx,  i);
	}
	for(auto i:t){
		discrete.push_back(i);
		mx = max(mx,  i);
	}

	discrete.push_back(1);
    discrete.push_back(mx + 1);
	s.push_back(mx + 1);
	t.push_back(1);
	sort(ALL(discrete));
	discrete.erase(unique(ALL(discrete)), discrete.end());
	
	int C = discrete.size();
	for(int i = 0; i < C; i++){
		dsu[i] = -1;
	}
	long long ans = 0;
	assert(n == s.size());
	for(int i = 0; i < n; i++){
		direct[get_id(s[i])]++;
		direct[get_id(t[i])]--;
		merge(get_id(s[i]), get_id(t[i]));
	}
	vector <pair<int, pair<int, int>>> connect_cc;
	for(int i = 0; i < C - 1; i++){
		ans += max(direct[i], 0) * dist(i, i + 1);
		if(direct[i])
			merge(i, i + 1);	
		direct[i + 1] += direct[i]; 
		connect_cc.push_back({dist(i, i + 1), {i, i + 1}});
	}
	sort(ALL(connect_cc));
	for(auto i:connect_cc){
		  if(merge(i.sc.fs, i.sc.sc))
			ans += i.fs;
	}
	uwu ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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