# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
110489 | 2019-05-10T22:19:48 Z | MetB | Teleporters (IOI08_teleporters) | C++14 | 704 ms | 58472 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[3000000]; vector <int> v; int nxt[3000001], c[3000000], u[3000000]; int level[3000000], to[3000001]; 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; 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; i++) { if (u[i]) continue; 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]]; else v.push_back (level[x] - level[to[x]] + 1); } color++; } sort (v.begin(), v.end()); for (int i = v.size () - 1; i >= 0 && m; i--) { ans += v[i] + 2; m--; } cout << ans + m / 2 * 4 + m % 2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 8144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 8268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 8320 KB | Output is correct |
2 | Correct | 16 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8320 KB | Output is correct |
2 | Correct | 16 ms | 8576 KB | Output is correct |
3 | Correct | 21 ms | 9472 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 8568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 73 ms | 12496 KB | Output is correct |
2 | Correct | 208 ms | 22556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 124 ms | 15476 KB | Output is correct |
2 | Correct | 315 ms | 22796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 406 ms | 29832 KB | Output is correct |
2 | Correct | 485 ms | 34136 KB | Output is correct |
3 | Correct | 569 ms | 49928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 704 ms | 37912 KB | Output is correct |
2 | Correct | 639 ms | 40280 KB | Output is correct |
3 | Correct | 625 ms | 53496 KB | Output is correct |
4 | Correct | 671 ms | 54264 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 688 ms | 43944 KB | Output is correct |
2 | Correct | 680 ms | 43932 KB | Output is correct |
3 | Correct | 261 ms | 58208 KB | Output is correct |
4 | Correct | 637 ms | 58472 KB | Output is correct |