# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
110477 | 2019-05-10T21:55:06 Z | MetB | Teleporters (IOI08_teleporters) | C++14 | 637 ms | 46248 KB |
#include <iostream> #include <cstdlib> #include <string> #include <set> #include <map> #include <algorithm> #include <bitset> #include <queue> #include <math.h> #include <stack> #include <vector> #include <string.h> #include <random> typedef long long ll; const ll MOD = 1e9 + 7, INF = 1e18; using namespace std; int n, m, mn, ans; pair <int, int> a[1000000]; int nxt[1000001], prev[1000000], c[1000000], u[1000000], v[2000001]; int level[1000000], to[1000000]; int main () { cin >> n >> m; for (int i = 0; i < n; i++) { scanf ("%d%d", &a[i].first, &a[i].second); nxt[a[i].first - 1] = 2 * i + 1; nxt[a[i].second - 1] = 2 * i + 2; if (a[mn].first > a[i].first) mn = i; } for (int i = 2000000 - 1; i >= 0; i--) if (!nxt[i]) nxt[i] = nxt[i + 1]; to[0] = 2 * mn + 1; cout << to[0] << endl; for (int i = 0; i < n; i++) { to[2 * i + 1] = nxt[a[i].second]; to[2 * i + 2] = nxt[a[i].first]; } int color = 1; for (int i = 0; i < 2 * n + 1; i++) { int x = i; u[x] = color; while (!u[to[x]]) { level[to[x]] = level[x] + 1; u[to[x]] = color; x = to[x]; } if (u[to[x]] == color) { if (color == 1) ans = level[x] - level[to[x]] + 1; else v[level[x] - level[to[x]] + 1]++; } color++; } for (int i = n; i >= 1 && m; i--) while (v[i]) { m--; v[i]--; ans += i + 2; } cout << ans - 1 + m / 2 * 4 + m % 2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 8320 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8188 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 8136 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8156 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 8184 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 8448 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 8320 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 8584 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 8824 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 67 ms | 12780 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 127 ms | 22460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 332 ms | 37796 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 539 ms | 43556 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 637 ms | 46248 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |