Submission #355572

#	Time	Username	Problem	Language	Result	Execution time	Memory
355572		tengiz05	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	341 ms	44124 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<int> 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;
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
	s = sk, t = tk;
	n = s.size();
	seg.init(n*2);
	for(int i=0;i<n;i++){
		all.push_back(s[i]);
		all.push_back(t[i]);
	}
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	vector<int> v;
	for(int i=0;i<n;i++){
		v.push_back(s[i]);
		v.push_back(t[i]);
	}sort(v.begin(), v.end());
	for(int i=0;i<n;i++){
		s[i] = lower_bound(v.begin(), v.end(), s[i])-v.begin();
		t[i] = lower_bound(v.begin(), v.end(), t[i])-v.begin();
		if(s[i] < t[i]){
			seg.update(s[i], t[i]-1, 1);
		}else if(s[i] > t[i]){
			seg.update(t[i], s[i]-1, -1);	
		}edges[s[i]].push_back(t[i]);
	}
	edges[n-1].push_back(0);
	seg.update(0,n-1,-1);
	for(int i=0;i<n-1;i++){
		if(seg.get(i) > 0){
			return 1000000000;
		}if(seg.get(i) < 0){
			edges[i].push_back(i+1);
		}
	}
	/// 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(int i=0;i<n;i++){
		if(!used[i])return 987654321;
	}
	//~ for(int i=0;i<n;i++){
		//~ for(auto v : edges[i]){
			//~ rev[v].push_back(i);
		//~ }
	//~ }
	//~ 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(int i=0;i<n;i++){
		//~ if(!used[i])return 123456789;
	//~ }
	//~ /// check for eulerian circuit
	//~ for(int i=0;i<n;i++){
		//~ ll s1 = edges[i].size(), s2 = rev[i].size();
		//~ if(s1 != s2)return 999999999;
	//~ }
	return 0;
}

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