Submission #609292

#	Time	Username	Problem	Language	Result	Execution time	Memory
609292		amunduzbaev	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	178 ms	61476 KiB

railroad

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

#ifndef EVAL
#include "grader.cpp"
#endif

typedef long long ll;
#define ar array

const ll inf = 1e18;

namespace S1{

const int N = 16;
ll dp[1 << N][N];

ll solve(vector<int> s, vector<int> t){
	int n = s.size();
	memset(dp, 15, sizeof dp);
	
	for(int i=0;i<n;i++){
		dp[(1 << i)][i] = 0;
	}
	
	for(int mask=1;mask < (1 << n);mask++){
		for(int i=0;i<n;i++){
			if(mask >> i & 1){
				for(int j=0;j<n;j++){
					if((mask >> j & 1) && i != j){
						dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + max(0, t[j] - s[i]));
					}
				}
			}
		}
	}
	
	ll res = inf;
	for(int i=0;i<n;i++){
		res = min(res, dp[(1 << n) - 1][i]);
	}
	
	return res;
}

};

namespace S2{

const int N = 4e5 + 5;
vector<int> edges[N], G[N], ss;
int dp[N], used[N], tin[N], fup[N], t;
int cmp[N], last, cnt[N];

void dfs(int u){
	used[u] = 1, tin[u] = fup[u] = ++t;
	ss.push_back(u);
	for(auto x : edges[u]){
		if(used[x]){
			if(cmp[x]) continue;
			fup[u] = min(fup[u], tin[x]);
		} else {
			dfs(x);
			fup[u] = min(fup[u], fup[x]);
		}
	}
	
	if(tin[u] == fup[u]){
		int v; ++last;
		do{
			v = ss.back(); ss.pop_back();
			cmp[v] = last;
		}while(v != u);
	}
}

ll solve(vector<int> s, vector<int> t){
	int n = s.size();
	vector<ar<int, 2>> a(n);
	for(int i=0;i<n;i++) a[i] = {s[i], t[i]};
	sort(a.begin(), a.end());
	
	for(int i=0;i<n;i++){
		if(i + 1 < n) edges[i + n].push_back(i + n + 1);
		edges[i + n].push_back(i);
		int j = lower_bound(a.begin(), a.end(), (ar<int, 2>){a[i][1], -1}) - a.begin();
		if(j < n) edges[i].push_back(j + n);
	}
	
	for(int i=0;i<n + n;i++){
		if(used[i]) continue;
		dfs(i);
	}
	
	for(int i=0;i<n + n;i++){
		cnt[cmp[i]] += (i < n);
		for(auto x : edges[i]){
			if(cmp[i] != cmp[x]){
				G[cmp[i]].push_back(cmp[x]);
			}
		}
	}
	
	t.clear();
	memset(used, 0, sizeof used);
	function<void(int)> dfs = [&](int u){
		used[u] = 1;
		for(auto x : G[u]){
			if(used[x]) continue;
			dfs(x);
		}
		
		t.push_back(u);
	};
	
	for(int i=1;i<=last;i++){
		if(used[i]) continue;
		dfs(i);
	}
	
	for(auto u : t){
		dp[u] = cnt[u];
		for(auto x : G[u]){
			dp[u] = max(dp[u], dp[x] + cnt[u]);
		}
	}
	
	if(dp[t.back()] == n) return 0;
	return 1;
}

};

/*

4
1 7
4 3
5 8
6 6

*/

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = s.size();
	
	if(n <= 16){
		return S1::solve(s, t);
	}
	
	return S2::solve(s, t);
}

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