| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1231579 | LIA | Roller Coaster Railroad (IOI16_railroad) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector <int> p , sz;
DSU (int n): p(n), sz(n ,1) { iota(p.begin() ,p.end() ,0); }
int find (int x) { return x == p[x] ? x : p[x] = find(p[x]); }
void unite (int a,int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a ,b);
p[b] = a;
sz[a] += sz[b];
}
};
long long plan_roller_coaster (vector <long long> s,vector <long long> t) {
int n = s.size();
const long long INF = 2000000005LL;
vector <long long> v;
v.reserve(2 * n + 2);
v.push_back(1);
for (int i = 0 ; i < n ; i++) {
v.push_back(s[i]);
v.push_back(t[i]);
}
v.push_back(INF);
sort(v.begin() ,v.end());
v.erase(unique(v.begin() ,v.end()) ,v.end());
int m = v.size();
auto id = [&] (long long x) { return int(lower_bound(v.begin() ,v.end() ,x) - v.begin()); };
vector <long long> diff(m + 1 ,0);
DSU dsu(m);
vector <int> used;
used.reserve(2 * n + 2);
for (int i = 0 ; i < n ; i++) {
int a = id(s[i]) , b = id(t[i]);
used.push_back(a);
used.push_back(b);
dsu.unite(a ,b);
if (t[i] > s[i]) {
diff[a]++;
diff[b]--;
} else if (t[i] < s[i]) {
diff[a]--;
diff[b]++;
}
}
int a = id(INF) , b = id(1LL);
used.push_back(a);
used.push_back(b);
dsu.unite(a ,b);
diff[a]--;
diff[b]++;
long long bal = 0;
for (int i = 0 ; i < m - 1 ; i++) {
bal += diff[i];
if (bal) return 1;
}
int root = dsu.find(used[0]);
for (int x : used) if (dsu.find(x) != root) return 1;
return 0;
}