# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
58271 | 2018-07-17T10:34:47 Z | memikakizaki | Teleporters (IOI08_teleporters) | C++14 | 823 ms | 66560 KB |
#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]; int cycles[N], idx; 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]; } 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; 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[idx++] = sz; else ans = sz-1; } sort(cycles, cycles+idx, greater<int>()); for(int i = 0; i < min(idx, m); i++) ans += cycles[i] + 2; if(m > idx) { m -= idx; ans += ((m - (m & 1)) << 1) + (m & 1); } printf("%lld", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 772 KB | Output is correct |
2 | Correct | 9 ms | 1052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1052 KB | Output is correct |
2 | Correct | 11 ms | 1528 KB | Output is correct |
3 | Correct | 16 ms | 2212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 2212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 2212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 66 ms | 6360 KB | Output is correct |
2 | Correct | 190 ms | 15132 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 118 ms | 15132 KB | Output is correct |
2 | Correct | 310 ms | 20228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 413 ms | 25484 KB | Output is correct |
2 | Correct | 509 ms | 28972 KB | Output is correct |
3 | Correct | 553 ms | 30560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 708 ms | 31624 KB | Output is correct |
2 | Correct | 823 ms | 47608 KB | Output is correct |
3 | Correct | 606 ms | 60824 KB | Output is correct |
4 | Runtime error | 647 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 695 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 | Halted | 0 ms | 0 KB | - |