Submission #1041519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041519		pcc	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	117 ms	23488 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>

const ll inf = 1e9+10;
const int mxn = 2e5+10;

struct DSU{
	int dsu[mxn*3],sz[mxn*3];
	void init(int n){
		iota(dsu,dsu+n,0);
		fill(sz,sz+n,1);
	}
	int root(int k){return k== dsu[k]?k:dsu[k] = root(dsu[k]);}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a] += sz[b];
		dsu[b] = a;
		return;
	}
	DSU(){}
};

DSU dsu;
vector<int> all;
int deg[mxn*3];
int in[mxn*3],out[mxn*3];
vector<tuple<int,int,int>> edges;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	ll ans = 0;
	int N = (int)s.size();
	all.push_back(0);
	for(int i = 0;i<N;i++){
		all.push_back(s[i]);
		all.push_back(t[i]);
	}
	all.push_back(inf);
	sort(_all(all));all.erase(unique(_all(all)),all.end());
	dsu.init(all.size());
	for(int i = 0;i<N;i++){
		s[i] = lower_bound(_all(all),s[i])-all.begin();
		t[i] = lower_bound(_all(all),t[i])-all.begin();
		out[s[i]]++;
		in[t[i]]++;
		dsu.onion(s[i],t[i]);
	}
	in[0]++;out[all.size()-1]++;
	for(int i = 0;i<all.size();i++){
		if(i != all.size()-1||in[i] == out[i]);
		if(in[i] == out[i])continue;
		else if(in[i]<out[i]){
			int d = out[i]-in[i];
			ans += 1ll*(all[i+1]-all[i])*d;
			in[i] += d;
			out[i+1] += d;
			dsu.onion(i,i+1);
		}
		else{
			int d = in[i]-out[i];
			out[i] += d;
			in[i+1] += d;
			dsu.onion(i,i+1);
		}
	}
	for(int i = 1;i<all.size();i++){
		if(dsu.root(i) != dsu.root(i-1)){
			edges.push_back(tiii(all[i]-all[i-1],i,i-1));
		}
	}
	sort(edges.begin(),edges.end());
	for(auto &[w,a,b]:edges){
		if(dsu.root(a) != dsu.root(b)){
			dsu.onion(a,b);
			ans += w;
		}
	}
	return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
railroad.cpp:60:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if(i != all.size()-1||in[i] == out[i]);
      |      ~~^~~~~~~~~~~~~~~
railroad.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 1;i<all.size();i++){
      |                ~^~~~~~~~~~~

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