# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
58259 | 2018-07-17T10:04:58 Z | memikakizaki | Teleporters (IOI08_teleporters) | C++14 | 839 ms | 66560 KB |
#include <bits/stdc++.h> #define long long long using namespace std; const int N = 1e6+10, 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] = 2e6+2; sort(vals, vals+2*n); for(int i = 0; i <= n << 1; i++) rev[vals[i]] = i; for(int i = 0; i < n; i++) { nxt[rev[lf[i]]] = rev[rg[i]]+1; nxt[rev[rg[i]]] = rev[lf[i]]+1; } 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.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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 600 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 600 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 724 KB | Output is correct |
2 | Correct | 10 ms | 1108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1108 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 5908 KB | Output is correct |
2 | Correct | 221 ms | 14852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 132 ms | 14852 KB | Output is correct |
2 | Incorrect | 354 ms | 19632 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 427 ms | 25296 KB | Output is correct |
2 | Correct | 533 ms | 39440 KB | Output is correct |
3 | Correct | 549 ms | 53496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 688 ms | 54200 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 791 ms | 59220 KB | Output is correct |
2 | Runtime error | 839 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. |
3 | Halted | 0 ms | 0 KB | - |