# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
56492 | 2018-07-11T13:17:26 Z | aquablitz11 | Teleporters (IOI08_teleporters) | C++14 | 752 ms | 43060 KB |
#include <stdio.h> #include <stdlib.h> #define N 1000001 int n, m; int A[N], B[N], pos[2*N], coord[2*N], cc; int comp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d%d", &A[i], &B[i]); coord[2*i+1] = A[i]; coord[2*i+2] = B[i]; } qsort(coord, 2*n+1, sizeof(int), comp); for (int i = 0; i < 2*n+1; ++i) pos[coord[i]] = i; for (int i = 0; i < n; ++i) { A[i] = pos[A[i]]; B[i] = pos[B[i]]; } for (int i = 0; i < n; ++i) { pos[A[i]-1] = B[i]; pos[B[i]-1] = A[i]; } for (int i = 0; i < 2*n+1; ++i) coord[i] = 0; int ans = 0; for (int s = 0; s < 2*n; ++s) { if (coord[s]) continue; for (int u = s, c = 1; ; ++c) { coord[u] = 1; u = pos[u]; if (coord[u]) { A[cc++] = c; break; } else if (u == 2*n) { ans = c; break; } } } qsort(A, cc, sizeof(int), comp); while (m--) { if (cc > 0) { ans += A[--cc]+2; } else { ++ans; A[cc++] = 1; } } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 412 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 476 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 520 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 736 KB | Output is correct |
2 | Correct | 8 ms | 1004 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1004 KB | Output is correct |
2 | Correct | 10 ms | 1392 KB | Output is correct |
3 | Correct | 17 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 75 ms | 4732 KB | Output is correct |
2 | Correct | 199 ms | 12228 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 149 ms | 12228 KB | Output is correct |
2 | Correct | 300 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 414 ms | 19972 KB | Output is correct |
2 | Correct | 570 ms | 22204 KB | Output is correct |
3 | Correct | 583 ms | 23208 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 752 ms | 23560 KB | Output is correct |
2 | Correct | 705 ms | 25160 KB | Output is correct |
3 | Correct | 705 ms | 25160 KB | Output is correct |
4 | Correct | 720 ms | 25160 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 739 ms | 26664 KB | Output is correct |
2 | Correct | 726 ms | 27008 KB | Output is correct |
3 | Correct | 569 ms | 40988 KB | Output is correct |
4 | Correct | 714 ms | 43060 KB | Output is correct |