# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
320268 | 2020-11-08T07:05:02 Z | AlexLuchianov | Teleporters (IOI08_teleporters) | C++14 | 623 ms | 53484 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); if(aux.size() == 2) std::cout << aux[0] << " " << aux[1] << '\n'; 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]; m--; } std::cout << result + m * 2 - m % 2; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 364 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 504 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 488 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 492 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 624 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 736 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 720 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 768 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 772 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 776 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 780 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 912 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1868 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 2100 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 59 ms | 8004 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 114 ms | 13492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 371 ms | 38432 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 563 ms | 46472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 623 ms | 53484 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |