# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
772546 | 2023-07-04T08:13:58 Z | kingfran1907 | Teleporters (IOI08_teleporters) | C++14 | 879 ms | 64052 KB |
#include <bits/stdc++.h> using namespace std; typedef long long llint; const int maxn = 25e5+10; const int inf = 0x3f3f3f3f; int n, m; int l[maxn], r[maxn]; vector< int > v; vector< pair<int, int> > vs; int nex[maxn]; bool bio[maxn]; priority_queue< int > cycles; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d%d", l+i, r+i); l[n] = -1; r[n] = inf; n++; for (int i = 0; i < n; i++) { v.push_back(l[i]); v.push_back(r[i]); } sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin(); r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin(); vs.push_back({l[i], i}); vs.push_back({r[i], i}); } sort(vs.begin(), vs.end()); for (int i = 0; i < v.size() - 1; i++) { int ind = vs[i + 1].second; int rs = l[ind] + r[ind] - vs[i + 1].first; nex[i] = rs; } int sol = 0; for (int i = 0; i < v.size() - 1; i++) { //printf("trying: %d\n", i); if (bio[i]) continue; int cnt = 0; int ptr = i; //printf("cycle: "); while (!bio[ptr]) { //printf("%d ", ptr); bio[ptr] = true; ptr = nex[ptr]; cnt++; } //printf("\n"); if (i > 0) cycles.push(cnt); else sol = cnt - 1; } while (m && !cycles.empty()) { //printf("debug: %d\n", cycles.top()); sol += cycles.top() + 2; cycles.pop(); m--; } //printf("%d - %d\n", m, cycles.size()); m = m -= min(m, (int)cycles.size()); sol += 2 * (m - m % 2) + m % 2; printf("%d\n", sol); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 312 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 7 ms | 952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 596 KB | Output is correct |
2 | Correct | 7 ms | 1104 KB | Output is correct |
3 | Correct | 18 ms | 2016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 84 ms | 7616 KB | Output is correct |
2 | Correct | 225 ms | 17864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 155 ms | 12832 KB | Output is correct |
2 | Correct | 370 ms | 26224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 484 ms | 38748 KB | Output is correct |
2 | Correct | 596 ms | 46016 KB | Output is correct |
3 | Correct | 659 ms | 53064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 720 ms | 52700 KB | Output is correct |
2 | Correct | 787 ms | 57340 KB | Output is correct |
3 | Correct | 765 ms | 55384 KB | Output is correct |
4 | Correct | 755 ms | 56068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 879 ms | 62472 KB | Output is correct |
2 | Correct | 809 ms | 62784 KB | Output is correct |
3 | Correct | 453 ms | 64052 KB | Output is correct |
4 | Correct | 804 ms | 63948 KB | Output is correct |