# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
320270 | 2020-11-08T07:06:06 Z | AlexLuchianov | Teleporters (IOI08_teleporters) | C++14 | 635 ms | 65536 KB |
#include <iostream> #include <vector> #include <cassert> #include <cmath> #include <set> #include <map> #include <algorithm> using ll = long long; #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) < (b)) ? (b) : (a)) int const nmax = 1000000; int edge[5 + 2 * nmax], seen[5 + nmax * 2]; int extract(int node) { int start = node; int _count = 0; std::vector<int> aux; do { seen[node] = 1; _count++; node = edge[node]; aux.push_back(node); } while(start != node); return _count; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int n, m; std::cin >> n >> m; std::vector<std::pair<int,int>> points; points.push_back({0, 0}); points.push_back({nmax * 2 + 1, 1}); for(int i = 1;i <= n; i++) { int start, stop; std::cin >> start >> stop; points.push_back({start, i * 2}); points.push_back({stop, i * 2 + 1}); } std::sort(points.begin(), points.end()); for(int i = 0; i < points.size() - 1; i++) edge[points[i].second] = (points[i + 1].second ^ 1); int result = extract(0) - 1; std::vector<int> cycles; for(int i = 2; i <= 2 * n + 1; i++) if(seen[i] == 0) cycles.push_back(extract(i)); std::sort(cycles.begin(), cycles.end()); std::reverse(cycles.begin(), cycles.end()); for(int i = 0; i < cycles.size() && 0 < m; i++) { result += cycles[i] + 2; m--; } std::cout << result + m * 2 - m % 2; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 372 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 844 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 844 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 844 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 972 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1080 KB | Output is correct |
2 | Correct | 5 ms | 1468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1216 KB | Output is correct |
2 | Correct | 5 ms | 1884 KB | Output is correct |
3 | Correct | 12 ms | 3188 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 6596 KB | Output is correct |
2 | Correct | 161 ms | 17264 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 13568 KB | Output is correct |
2 | Correct | 248 ms | 30156 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 358 ms | 35792 KB | Output is correct |
2 | Correct | 458 ms | 51184 KB | Output is correct |
3 | Correct | 478 ms | 63392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 547 ms | 61356 KB | Output is correct |
2 | Correct | 598 ms | 65536 KB | Output is correct |
3 | Correct | 635 ms | 65536 KB | Output is correct |
4 | Correct | 567 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 626 ms | 56248 KB | Output is correct |
2 | Correct | 630 ms | 65536 KB | Output is correct |
3 | Correct | 419 ms | 65536 KB | Output is correct |
4 | Correct | 590 ms | 65484 KB | Output is correct |