# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
396601 | 2021-04-30T11:53:05 Z | Berted | Teleporters (IOI08_teleporters) | C++14 | 733 ms | 42808 KB |
#include <iostream> #include <algorithm> #include <vector> #include <bitset> #define pii pair<int, int> #define fst first #define snd second using namespace std; const int MX = 2000000; int N, K, res = 0; int nex[2000005]; pii A[2000005]; bitset<2000005> vis; vector<int> cyc; int main() { ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for (int i = 0; i < N; i++) { cin >> A[2 * i].fst >> A[2 * i].snd; A[2 * i + 1] = {A[2 * i].snd, A[2 * i].fst}; } A[2 * N] = {0, 0}; A[2 * N + 1] = {MX + 1, -1}; sort(A, A + 2 * N + 1); for (int i = 0; i < 2 * N + 2; i++) { if (A[i].snd != -1) nex[i] = upper_bound(A, A + 2 * N + 1, make_pair(A[i].snd, MX + 1)) - A; else nex[i] = -1; } int u = 0; while (u != -1) {res++; vis[u] = 1; u = nex[u];} for (int i = 1; i < 2 * N + 1; i++) { if (!vis[i]) { u = i; int s = 0; while (!vis[u]) {vis[u] = 1; u = nex[u]; s++;} cyc.push_back(s); } } sort(cyc.begin(), cyc.end(), greater<int>()); for (int i = 0; i < cyc.size() && i < K; i++) res += cyc[i]; cout << res + 2 * K - 2 << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 328 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 460 KB | Output is correct |
2 | Correct | 6 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 972 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 72 ms | 5348 KB | Output is correct |
2 | Correct | 197 ms | 12376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 131 ms | 8904 KB | Output is correct |
2 | Incorrect | 321 ms | 18000 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 391 ms | 26228 KB | Output is correct |
2 | Correct | 493 ms | 31284 KB | Output is correct |
3 | Correct | 472 ms | 35640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 722 ms | 36164 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 733 ms | 42808 KB | Output is correct |
2 | Correct | 725 ms | 42764 KB | Output is correct |
3 | Correct | 527 ms | 42612 KB | Output is correct |
4 | Correct | 564 ms | 42752 KB | Output is correct |