# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
58266 | memikakizaki | Teleporters (IOI08_teleporters) | C++14 | 765 ms | 66560 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>
#define long long long
using namespace std;
const int N = 1e6+3, INF = 1e9;
int n, m, lf[N], rg[N], vals[2*N], rev[2*N], nxt[2*N];
vector<int> cycles;
bitset<N<<1> mark;
long ans;
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%d %d", &lf[i], &rg[i]);
vals[i<<1] = lf[i];
vals[i<<1|1] = rg[i];
}
vals[2*n] = -1;
sort(vals, vals+2*n+1);
for(int i = 0; i <= n << 1; i++) rev[vals[i]] = i;
for(int i = 0; i < n; i++) {
nxt[rev[lf[i]]-1] = rev[rg[i]];
nxt[rev[rg[i]]-1] = rev[lf[i]];
}
nxt[2*n] = INF;
cycles.reserve(n);
for(int i = 0; i <= n << 1; i++) if(!mark[i]) {
int curr = i, sz = 0;
bool cycle = false;
while(curr != INF) {
if(mark[curr]) {
cycle = true;
break;
}
++sz;
mark[curr] = true;
curr = nxt[curr];
}
if(cycle) cycles.push_back(sz);
else ans = sz-1;
}
sort(cycles.begin(), cycles.end(), greater<int>());
for(int i = 0; i < min((int) cycles.size(), m); i++) ans += cycles[i] + 2;
if(m > cycles.size()) {
m -= cycles.size();
ans += (m - (m & 1)) << 1 + (m & 1);
}
printf("%lld", ans);
}
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... |
# | 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... |
# | 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... |
# | 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... |
# | 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... |