# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
239233 | 2020-06-14T21:54:01 Z | osaaateiasavtnl | Teleporters (IOI08_teleporters) | C++14 | 916 ms | 50144 KB |
#include<bits/stdc++.h> using namespace std; #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int C = 2e6+7; int who[C]; signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int n, m; cin >> n >> m; vector <ii> a(n); vector <int> c = {0, 2 * 1000 * 1000 + 1}; for (int i = 0; i < n; ++i) { cin >> a[i].f >> a[i].s; c.app(a[i].f); c.app(a[i].s); who[a[i].f] = i; who[a[i].s] = i; } sort(all(c)); int sz = c.size() - 1; vector <int> to(sz, -1); for (int i = 0; i + 2 < c.size(); ++i) { int u = who[c[i+1]]; int x = a[u].f^a[u].s^c[i+1]; to[i] = lower_bound(all(c), x) - c.begin(); } int ans = 0; vector <int> len; vector <bool> used(sz); for (int i = 0; i < sz; ++i) { if (!used[i]) { int u = i; int l = 0; while (u != -1 && !used[u]) { used[u] = 1; ++l; u = to[u]; } if (u == -1) { ans += l; } else { len.app(l); } } } sort(all(len)); reverse(all(len)); #ifdef HOME cout << "len : "; for (auto e : len) cout << e << ' '; cout << endl; #endif int ptr = 0; for (int i = 0; i < m; ++i) { if (ptr < len.size()) { ans += len[ptr] + 2; ++ptr; } else { ++ans; len.app(1); } } cout << ans - 1 << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 512 KB | Output is correct |
2 | Correct | 10 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 640 KB | Output is correct |
2 | Correct | 14 ms | 1276 KB | Output is correct |
3 | Correct | 23 ms | 1792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 1660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 1244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 7408 KB | Output is correct |
2 | Correct | 259 ms | 19348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 167 ms | 16352 KB | Output is correct |
2 | Correct | 392 ms | 26896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 508 ms | 33240 KB | Output is correct |
2 | Correct | 640 ms | 34148 KB | Output is correct |
3 | Correct | 585 ms | 37480 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 916 ms | 39232 KB | Output is correct |
2 | Correct | 907 ms | 48600 KB | Output is correct |
3 | Correct | 731 ms | 50144 KB | Output is correct |
4 | Correct | 677 ms | 46572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 868 ms | 42700 KB | Output is correct |
2 | Correct | 857 ms | 42476 KB | Output is correct |
3 | Correct | 503 ms | 43736 KB | Output is correct |
4 | Correct | 713 ms | 43784 KB | Output is correct |