# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80151 | 2018-10-19T07:36:48 Z | Sherazin | Teleporters (IOI08_teleporters) | C++14 | 1000 ms | 66560 KB |
#include <bits/stdc++.h> #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 2e6+5; int n, m; int chk[N], sz[N], mp[N], comp; vector<int> pos; int get(int x) { return lower_bound(pos.begin(), pos.end(), x) - pos.begin(); } int main() { scanf("%d %d", &n, &m); for(int i = 1, a, b; i <= n; i++) { scanf("%d %d", &a, &b); pos.emplace_back(a), pos.emplace_back(b); mp[a] = b, mp[b] = a; } pos.emplace_back(N-1); sort(pos.begin(), pos.end()); for(int i = 0; i < 2*n; i++) if(!chk[i]) { chk[i] = ++comp; queue<int> Q; Q.emplace(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); ++sz[comp]; int v = get(mp[pos[u]]) + 1; if(chk[v] || v == 2*n) continue; chk[v] = comp; Q.emplace(v); } } int ans = sz[1]; vector<int> V; for(int i = 2; i <= comp; i++) V.emplace_back(sz[i]); sort(V.begin(), V.end(), greater<int>()); for(int i = 0; i < V.size() && m; i++, m--) ans += V[i] + 2; if(m) ans += 2*(m - (m & 1)) + (m & 1); printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 472 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 472 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 472 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 792 KB | Output is correct |
2 | Correct | 9 ms | 1336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1336 KB | Output is correct |
2 | Correct | 12 ms | 1752 KB | Output is correct |
3 | Correct | 20 ms | 2148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 2148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 2148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 7908 KB | Output is correct |
2 | Correct | 331 ms | 20228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 219 ms | 20228 KB | Output is correct |
2 | Correct | 499 ms | 33368 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 672 ms | 49220 KB | Output is correct |
2 | Correct | 808 ms | 62584 KB | Output is correct |
3 | Runtime error | 1000 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1097 ms | 66560 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1089 ms | 66560 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |