Submission #469115

#	Time	Username	Problem	Language	Result	Execution time	Memory
469115		Leonardo_Paes	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	574 ms	59112 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
map<int,int> m;
const int maxn = 4e5 + 10;
vector<int> grafo[maxn];
bool mark[maxn];
void dfs(int u){
	mark[u] = 1;
	for(int v : grafo[u]){
		if(mark[v]) continue;
		dfs(v);
	}
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = (int)s.size() + 1;
	s.push_back(1e9);
	t.push_back(1);
	vector<int> v;
	for(int x : s) v.push_back(x);
	for(int x : t) v.push_back(x);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int tt = 0;
	for(int x : v) m[x] = ++tt;
	vector<int> sum(tt+1, 0);
	for(int i=0; i<n; i++){
		int u = m[s[i]], v = m[t[i]];
		if(u == v) continue;
		grafo[u].push_back(v);
		++sum[u], --sum[v];
	}
	bool ok = 0;
	for(int i=0; i<tt; i++){
		if(i) sum[i] += sum[i-1];
		if(sum[i] > 0) ok = 1;
		else if(sum[i] < 0) grafo[i].push_back(i+1);
	}
	dfs(m[s[0]]);
	for(auto x : m) ok |= !mark[x.second];
	return ok;
}

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