Submission #278830

#	Time	Username	Problem	Language	Result	Execution time	Memory
278830		mjkocijan	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1476 ms	142900 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 800200
#define INF 1001001001001001001LL

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

unordered_map<int, int> mp;

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

set<int> s2;
vector<int> s, z;
int ss[MAXN];

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]++;
}

vector<ii> 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);
  	s2.insert(_s[i]);
  	s2.insert(t[i]);
  	ss[_sz]++;
  	ss[tz]--;
  }
  
  for (int i: s2) { s.pb(i); z.pb(zip(i)); }
  
  int suma = 0;
  for (int j = 0; j < s.size() - 1; j++) {
  	int i = s[j];
  	int ni = s[j + 1];
  	suma += ss[z[j]];
  	if (suma > 0) {
  		reza += ll(suma) * ll(ni - i);
  		i = z[j];
  		ni = z[j + 1];
  		g[ni].pb(i);
  		in[i].pb(ni);
  		//cout<<i<<' '<<ni<<'='<<suma<<endl;
  	}
  	if (suma < 0) {
  		i = z[j];
  		ni = z[j + 1];
  		g[ni].pb(i);
  		in[i].pb(ni);
  	}
  }
  
  for (int j = 0; j < s.size(); j++) {
  	int i = s[j];
  	dfs(z[j], z[j]);
  	//cout << i<<' '<<rt[zip(i)]<<endl;
  }
  
  for (int j = 0; j < s.size() - 1; j++) {
  	int i = s[j];
  	int ni = s[j + 1];
  	es.pb({ll(ni) - i, j});//cout<<ll(ni)-i<<' '<<i<<'.'<<ni<<' '<<zip(i)<<'.'<<zip(ni)<<endl;
  }
  
  sort(es.begin(), es.end());
  
  int kk = 0;
  
  while (co.size() > 1) {
  	ii cu = es[kk];//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<endl;
  	kk++;//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<' '<<co.size()<<','<<reza<<endl;
  	int pre = co.size();
  	merg(z[cu.Y], z[cu.Y + 1]);
  	int nov = co.size();
  	if (nov < pre) reza += cu.X;
  }
  
  return reza;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int j = 0; j < s.size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~
railroad.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int j = 0; j < s.size(); j++) {
      |                   ~~^~~~~~~~~~
railroad.cpp:110:8: warning: unused variable 'i' [-Wunused-variable]
  110 |    int i = s[j];
      |        ^
railroad.cpp:115:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for (int j = 0; j < s.size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~

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