Submission #1050561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050561		Alihan_8	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	96 ms	10552 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'

struct Dsu{
	vector <int> fa;
	
	Dsu(int n){
		fa.resize(n);
		iota(all(fa), 0);
	}
	
	int get(int x){
		return x ^ fa[x] ? fa[x] = get(fa[x]) : x;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		fa[v] = u;
		
		return true;
	}
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	int n = s.size(), m;
	
	s.pb(2e9), t.pb(1);
	
	{ // compression
		vector <int> p_;
		
		for ( int i = 0; i <= n; i++ ){
			p_.pb(s[i]); p_.pb(t[i]);
		}
		
		sort(all(p_));
		p_.resize(unique(all(p_)) - p_.begin());
		
		m = p_.size();
		
		for ( int i = 0; i <= n; i++ ){
			s[i] = lower_bound(all(p_), s[i]) - p_.begin();
			t[i] = lower_bound(all(p_), t[i]) - p_.begin();
		}
 	}
 	
 	vector <int> pf(m);
 	
 	for ( int i = 0; i <= n; i++ ){
		pf[t[i]]--;
		pf[s[i]]++;
	}
	
	for ( int i = 1; i < m; i++ ){
		pf[i] += pf[i - 1];
	}
		
	Dsu ds(m);
	
	for ( int i = 0; i <= n; i++ ){
		ds.merge(s[i], t[i]);
	}
	
	for ( int i = 0; i + 1 < m; i++ ){
		if ( pf[i] > 0 ){
			return 1;
		}
		
		if ( pf[i] < 0 ) ds.merge(i, i + 1);
	}
	
	int root = ds.get(0);
	
	for ( int i = 0; i < m; i++ ){
		if ( ds.get(i) != root ){
			return 1;
		}
	}
	
	return 0;
}

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