# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
795198 | fatemetmhr | Roller Coaster Railroad (IOI16_railroad) | C++17 | 304 ms | 41976 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// ~ Be Name Khoda ~ //
#include "railroad.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
vector <int> num, adj[maxn5];
int cnt[maxn5];
bool mark[maxn5];
void dfs(int v){
mark[v] = true;
for(auto u : adj[v]) if(!mark[u])
dfs(u);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = s.size();
for(int i = 0; i < n; i++){
num.pb(s[i]);
num.pb(t[i]);
}
num.pb(0);
num.pb(mod);
sort(all(num));
num.resize(unique(all(num)) - num.begin());
for(int i = 0; i < n; i++) if(s[i] != t[i]){
s[i] = lower_bound(all(num), s[i]) - num.begin();
t[i] = lower_bound(all(num), t[i]) - num.begin();
adj[s[i]].pb(t[i]);
adj[t[i]].pb(s[i]);
cnt[t[i] + 1]--;
cnt[s[i] + 1]++;
}
adj[0].pb(int(num.size()) - 1);
adj[int(num.size()) - 1].pb(0);
cnt[1]--;
int cur = 0;
for(int i = 0; i < num.size(); i++){
cur += cnt[i];
if(cur > 0)
return 1;
//cout << i << ' ' << cur << endl;
if(i && cur){
adj[i].pb(i - 1);
adj[i - 1].pb(i);
}
}
dfs(0);
for(int i = 0; i < num.size(); i++) if(!mark[i])
return 1;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |