Submission #354537

#	Time	Username	Problem	Language	Result	Execution time	Memory
354537		tengiz05	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	938 ms	63572 KiB

railroad

#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int MAXN = 4e5+5;
ll inf = 1e18;
int n;
vector<int> s, t;
int pos_all[MAXN];
vector<int> edges[MAXN], rev[MAXN];
vector<pii> all;
bool used[MAXN];
void dfs(int u){
	used[u] = true;
	for(auto v : edges[u]){
		if(!used[v])dfs(v);
	}
}
void dfs_rev(int u){
	used[u] = true;
	for(auto v : rev[u]){
		if(!used[v])dfs_rev(v);
	}
}
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
	s = sk, t = tk;
	n = s.size();
	for(int i=0;i<n;i++){
		all.push_back({s[i], i});
		all.push_back({t[i], i+n});
		pos_all[i] = s[i];
		pos_all[i+n] = t[i];
		edges[i].push_back(i+n);
		rev[i+n].push_back(i);
	}
	sort(all.begin(), all.end());
	auto [no_need_1, fff] = all[0];
	auto [no_need_2, sss] = all[(int)all.size()-1];
	edges[sss].push_back(fff);
	rev[fff].push_back(sss);
	{ /// Making A = B
		multiset<int> getting, bgetting;
		int A=0, B=0;
		for(int i=0;i<(int)all.size()-1;i++){
			int ind1 = all[i].second;
			int ind2 = all[i+1].second;
			for(auto x : edges[ind1]){
				if(getting.count(x)){
					getting.erase(getting.find(x));
					B--;
				}else {
					if(pos_all[ind1] <= pos_all[x]){
						A++;
						bgetting.insert(ind1);
					}else assert(false);
				}
			}
			for(auto x : rev[ind1]){
				if(bgetting.count(x)){
					bgetting.erase(bgetting.find(x));
					A--;
				}else {
					if(pos_all[ind1] <= pos_all[x]){
						B++;
						getting.insert(ind1);
					}else assert(false);	
				}
			}
			//~ cout << A << '-' << B << '\n';
			if(A > B)return 1000000000;
			if(A < B){
				A++;
				edges[ind1].push_back(ind2);
				rev[ind2].push_back(ind1);
				bgetting.insert(ind1);
			}
		}
	}
	/// check for connectivity
	memset(used, 0, sizeof used);
	dfs(0);
	for(int i=0;i<n*2;i++){
		if(!used[i])return 987654321;
	}
	memset(used, 0, sizeof used);
	dfs_rev(0);
	for(int i=0;i<n*2;i++){
		if(!used[i])return 123456789;
	}
	/// now we need to start from arbitrary node and check for eulerian circuit
	int now = 0;
	while(!edges[now].empty()){
		int t = edges[now].back();
		edges[now].pop_back();
		now = t;
	}
	for(int i=0;i<n*2;i++){
		if(!edges[i].empty())return 999999999;
	}
	return 0;
}

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