Submission #469112

#	Time	Username	Problem	Language	Result	Execution time	Memory
469112		Leonardo_Paes	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	581 ms	54244 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();
    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);
   		if(u < v){
	   		++sum[u];
	   		--sum[v];
	   	}
	   	else{
	   		--sum[v];
	   		++sum[u];
	   	}
   	}
   	--sum[1];
   	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: 0 / 30
• Subtask 4: 0 / 36