# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
320258 | 2020-11-08T06:39:58 Z | AlexLuchianov | Teleporters (IOI08_teleporters) | C++14 | 1000 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; do { seen[node] = 1; _count++; node = edge[node]; } while(start != node); return _count; } int main() { 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() && i < m; i++) result += cycles[i]; std::cout << result + m * 2; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 540 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 548 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 552 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1124 KB | Output is correct |
2 | Correct | 9 ms | 1708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 1556 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1996 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 2288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 7716 KB | Output is correct |
2 | Correct | 291 ms | 18352 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 201 ms | 18420 KB | Output is correct |
2 | Incorrect | 455 ms | 32376 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 638 ms | 49620 KB | Output is correct |
2 | Correct | 806 ms | 64956 KB | Output is correct |
3 | Correct | 844 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 975 ms | 65536 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1056 ms | 65536 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |