Submission #355546

#	Time	Username	Problem	Language	Result	Execution time	Memory
355546		tengiz05	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	652 ms	96180 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;
vector<int> edges[MAXN], rev[MAXN];
vector<pii> Eedges[MAXN], Erev[MAXN];

vector<pii> all;
int used[MAXN];
struct segtree{
	int sz;
	vector<int> t;
	void init(int n){
		sz = n;
		t.assign(n*2,0);
	}
	void update(int l, int r, int val){
		assert(l <= r);
		for(l+=sz,r+=sz; l<=r; l>>=1,r>>=1){
			if(l%2==1)t[l++] += val;
			if(r%2==0)t[r--] += val;
		}return;
	}
	int get(int pos){
		int res = 0;
		for(pos += sz; pos > 0; pos >>= 1)res += t[pos];
		return res;
	}
}seg[2];
int pos[MAXN];
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
	s = sk, t = tk;
	n = s.size();
	seg[0].init(n*2);
	seg[1].init(n*2);
	for(int i=0;i<n;i++){
		all.push_back({s[i], i});
		all.push_back({t[i], i+n});
		edges[i].push_back(i+n);
		rev[i+n].push_back(i);
	}
	sort(all.begin(), all.end());
	for(int i=0;i<(int)all.size();i++){
		auto [x, y] = all[i];
		pos[y] = i;
	}
	auto [no_need_1, fff] = all[0];
	auto [no_need_2, sss] = all.back();
	edges[sss].push_back(fff);
	rev[fff].push_back(sss);
	for(int i=0;i<(int)all.size();i++){
		auto [u, p] = all[i];
		for(auto to : edges[p]){
			if(pos[to] > i){
				seg[0].update(i, pos[to]-1, 1);
			}else {
				seg[1].update(pos[to], i-1, 1);
			}
		}
	}
	{ /// Making A = B
		for(int i=0;i<(int)all.size()-1;i++){
			int ind1 = all[i].second;
			int ind2 = all[i+1].second;
			int A = seg[0].get(i);
			int B = seg[1].get(i);
			//~ if(i >= 15000)cout << i << ":  ";
			//~ if(i >= 15000)cout << A << '-' << B << '\n';
			//~ if(A > B)return 1000000000;
			if(A < B){
				Eedges[ind1].push_back({ind2,B-A});
				Erev[ind2].push_back({ind1,B-A});
				//~ seg[0].update(i,i,B-A);
				A = B;
			}
		}
	}
	/// check for connectivity
	queue<int> q;
	q.push(0);
	used[0] = true;
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto v : edges[u]){
			if(!used[v]){
				q.push(v);used[v] = true;
			}
		}for(auto [v,c] : Eedges[u]){
			if(!used[v]){
				q.push(v);used[v] = true;
			}
		}
	}
	for(int i=0;i<n;i++){
		if(!used[i])return 987654321;
	}
	memset(used, 0, sizeof used);
	q.push(0);
	used[0] = true;
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto v : rev[u]){
			if(!used[v]){
				q.push(v);used[v] = true;
			}
		}for(auto [v,c] : Erev[u]){
			if(!used[v]){
				q.push(v);used[v] = true;
			}
		}
	}
	for(int i=0;i<n*2;i++){
		if(!used[i])return 123456789;
	}
	/// check for eulerian circuit
	for(int i=0;i<n*2;i++){
		ll s1 = edges[i].size(), s2 = rev[i].size();
		for(auto [u, c] : Eedges[i])s1 += c;
		for(auto [u, c] : Erev[i])s2 += c;
		if(s1 != s2)return 999999999;
	}
	return 0;
}

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