# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
54075 | 2018-07-02T09:45:50 Z | imeimi2000 | Teleporters (IOI08_teleporters) | C++17 | 1000 ms | 26040 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; int n, m; int s[1000000]; int e[1000000]; int comp[2000000]; int to[2000000]; bool visited[2000001]; int arr[2000000]; int find(int x) { int s = 0, e = n << 1; while (s <= e) { int m = (s + e) / 2; if (comp[m] == x) return m; if (comp[m] < x) s = m + 1; else e = m - 1; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> s[i] >> e[i]; comp[i << 1 | 0] = s[i]; comp[i << 1 | 1] = e[i]; } comp[n << 1] = 0; sort(comp, comp + (n << 1 | 1)); for (int i = 0; i < n; ++i) { s[i] = find(s[i]); e[i] = find(e[i]); to[s[i]] = e[i]; to[e[i]] = s[i]; } visited[n << 1] = 1; int sz = -1; for (int i = 0; i < (n << 1); ++i) { if (visited[i]) continue; int x = to[i + 1]; visited[i] = 1; int s = 1; while (!visited[x]) { visited[x] = 1; x = to[x + 1]; ++s; } if (sz != -1) ++arr[s]; else sz = s; } for (int i = 2 * n - 1; i > 0 && m > 0; --i) { while (arr[i] > 0 && m > 0) { sz += i + 2; --arr[i]; --m; } } printf("%d\n", sz + ((m >> 1) << 2) + (m & 1)); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 748 KB | Output is correct |
2 | Correct | 8 ms | 876 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 876 KB | Output is correct |
2 | Correct | 10 ms | 876 KB | Output is correct |
3 | Correct | 20 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 1392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 3864 KB | Output is correct |
2 | Correct | 256 ms | 8340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 212 ms | 8340 KB | Output is correct |
2 | Correct | 507 ms | 12060 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 565 ms | 16492 KB | Output is correct |
2 | Correct | 704 ms | 19808 KB | Output is correct |
3 | Correct | 740 ms | 21452 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 902 ms | 22948 KB | Output is correct |
2 | Execution timed out | 1022 ms | 24876 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1082 ms | 26040 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |