Submission #278816

#	Time	Username	Problem	Language	Result	Execution time	Memory
278816		mjkocijan	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	459 ms	91296 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> ip;
#define MAXN 200200
#define INF 1001001001001001001LL

//ll dp[1 << MAXN][LOG], reza = INF;

unordered_map<int, int> mp;

vector<int> g[MAXN], in[MAXN];

set<int> s;
unordered_map<int, int> ss;

ll reza = 0;

int zip(int x)
{
	if (mp.count(x)) return mp[x];
	
	return mp[x] = mp.size();
}

int bio[MAXN];
int rt[MAXN], sz[MAXN];
set<int> co;

void dfs(int cv, int kor)
{
	if (bio[cv]) return;
	bio[cv] = 1;
	rt[cv] = kor;
	co.insert(kor);
	
	for (int i: g[cv])
		dfs(i, kor);
	for (int i: in[cv])
		dfs(i, kor);
}

int fn(int cv)
{
	if (cv == rt[cv]) return cv;
	
	return rt[cv] = fn(rt[cv]);
}

void merg(int x, int y)
{
	x = fn(x);
	y = fn(y);
	
	if (x == y) return;
	
	if (sz[x] > sz[y]) swap(x, y);
	
	rt[x] = y;
	co.erase(x);
	if (sz[x] == sz[y]) sz[y]++;
}

set<ip> es;

long long plan_roller_coaster(std::vector<int> _s, std::vector<int> t) {
  int n = (int) _s.size();
  _s.pb(1001001001); t.pb(1); n++;
  
  for (int i = 0; i < n; i++) {
  	int _sz = zip(_s[i]), tz = zip(t[i]);
  	g[_sz].pb(tz);
  	in[tz].pb(_sz);
  	s.insert(_s[i]);
  	s.insert(t[i]);
  	ss[_s[i]]++;
  	ss[t[i]]--;
  }
  
  int suma = 0;
  for (int i: s) {
  	suma += ss[i];
  	if (i == 1001001001) continue;
  	int ni = (*s.upper_bound(i));
  	if (suma > 0) {
  		reza += ll(suma) * ll(ni - i);
  		i = zip(i);
  		ni = zip(ni);
  		g[ni].pb(i);
  		in[i].pb(ni);
  		//cout<<i<<' '<<ni<<'='<<suma<<endl;
  	}
  	if (suma < 0) {
  		i = zip(i);
  		ni = zip(ni);
  		g[ni].pb(i);
  		in[i].pb(ni);
  	}
  }
  
  for (int i: s) {
  	dfs(zip(i), zip(i));
  	//cout << i<<' '<<rt[zip(i)]<<endl;
  }
  
  for (int i: s) {
  	if (i == 1001001001) continue;
  	int ni = (*s.upper_bound(i));
  	es.insert({ll(ni) - i, {zip(i), zip(ni)}});//cout<<ll(ni)-i<<' '<<i<<'.'<<ni<<' '<<zip(i)<<'.'<<zip(ni)<<endl;
  }
  
  while (co.size() > 1) {
  	ip cu = *es.begin();//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<endl;
  	es.erase(cu);//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<' '<<co.size()<<','<<reza<<endl;
  	int pre = co.size();
  	merg(cu.Y.X, cu.Y.Y);
  	int nov = co.size();
  	if (nov < pre) reza += cu.X;
  }
  
  return reza;
}

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