# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
110478 | 2019-05-10T21:55:51 Z | MetB | Teleporters (IOI08_teleporters) | C++14 | 583 ms | 31604 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; 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 | 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 | 14 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 | 13 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 12 ms | 8192 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 8164 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 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 | 15 ms | 8336 KB | Output isn't correct |
# | 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 | 14 ms | 8320 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 8528 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 8540 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 113 ms | 11152 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 128 ms | 19552 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 445 ms | 28756 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 548 ms | 30744 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 583 ms | 31604 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |