| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 910819 | Evirir | Teleporters (IOI08_teleporters) | C++17 | 0 ms | 0 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.
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
constexpr int _N = 2E6 + 5;
struct node {
int index, pos;
}a[_N];
inline bool cmp(const node& A, const node& B) { return A.pos < B.pos; }
int nxt[_N], N, M, sz[_N], vis[_N], cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
L(i, 1, N) {
static int l, r; cin >> l >> r;
a[i].index = i;
a[i].pos = l;
a[i + N].index = i + N;
a[i + N].pos = r;
}
sort(a + 1, a + 2 * N + 1, cmp);
L(i, 1, N * 2) {
//cerr << a[i].index << ' ';
if (a[i].index >= N + 1) {
int x = a[i].index - N, y = a[i].index;
a[i].index = y;
a[i].pos = x;
}
else {
int x = a[i].index, y = N + a[i].index;
a[i].index = x;
a[i].pos = y;
}
//cerr << a[i].left << ' ' << a[i].right << ' ';
}
//cerr << '\n';
a[0].pos = 0;
L(i, 1, 2 * N) nxt[a[i - 1].pos] = a[i].index;
nxt[a[2 * N].pos] = 0;
function<void(int)> dfs = [&vis, &sz, &cnt, &nxt](int u) {
if (vis[u]) return;
vis[u] = true;
sz[cnt]++;
if (!vis[nxt[u]]) dfs(nxt[u]);
};
memset(vis, 0, sizeof(vis));
memset(sz, 0, sizeof(sz));
L(i, 0, 2 * N) {
if (!vis[i]) {
cnt++;
sz[cnt] = 0;
dfs(i);
}
}
//~ L(i, 0, 2 * N){
//~ cerr << i << " has neighbours : ";
//~ for(auto & v : G[i]) cerr << v << ' ';
//~ cerr << '\n';
//~ }
sort(sz + 2, sz + cnt + 1, greater<int>());
int ans = sz[1] - 1;
//~ cerr << "cycle: ";
//~ for(auto & v: sz){
//~ cerr << v << ' ';
//~ }
//~ cerr << '\n';
L(i, 2, cnt) {
if (M == 0) break;
M--;
ans += sz[i];
ans += 2;
}
if (M & 1) { ans++; M--; }
ans += 2 * M;
cout << ans << '\n';
}