# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54053 | 2018-07-02T09:21:04 Z | 강태규(#1453) | Teleporters (IOI08_teleporters) | C++11 | 1000 ms | 30316 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 find(int x) { return lower_bound(comp, comp + (n << 1 | 1), x) - comp; } int dfs(int x) { if (visited[x]) return 0; visited[x] = 1; return dfs(to[x + 1]) + 1; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d%d", 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 = dfs(0); priority_queue<int> pq; for (int i = 1; i < (n << 1); ++i) { if (visited[i]) continue; pq.push(dfs(i)); } while (m) { if (pq.empty()) break; sz += pq.top() + 2; pq.pop(); --m; } printf("%d\n", sz + ((m >> 1) << 2) + (m & 1)); return 0; }
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 | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 620 KB | Output is correct |
2 | Correct | 9 ms | 968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 968 KB | Output is correct |
2 | Correct | 10 ms | 1024 KB | Output is correct |
3 | Correct | 21 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 4212 KB | Output is correct |
2 | Correct | 265 ms | 9020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 203 ms | 9020 KB | Output is correct |
2 | Correct | 481 ms | 12660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 668 ms | 18676 KB | Output is correct |
2 | Correct | 789 ms | 21876 KB | Output is correct |
3 | Correct | 774 ms | 25704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 979 ms | 25704 KB | Output is correct |
2 | Execution timed out | 1006 ms | 26908 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1087 ms | 30316 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |