# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54168 | 2018-07-02T14:57:12 Z | 0^0(#1448) | Teleporters (IOI08_teleporters) | C++11 | 1000 ms | 39996 KB |
#include <bits/stdc++.h> using namespace std; int n, m; pair<int, int> arr[1000005]; vector<pair<int, int> > vec; int par[2000005]; int sz[2000005]; int find(int x) { int temp = x; while (par[x] != x) x = par[x]; while (par[temp] != temp) { int ttemp = temp; temp = par[temp]; par[ttemp] = x; } return x; } void merge(int x, int y) { x = find(x); y = find(y); if (x == y)return; par[x] = y; sz[y] += sz[x]; } int main() { scanf("%d%d", &n, &m); vec.push_back({ 0,0 }); vec.push_back({ 2000001,1 }); par[0] = 0; par[1] = 1; for (int i = 1; i <= n; i++) { scanf("%d%d", &arr[i].first, &arr[i].second); vec.push_back({ arr[i].first, i * 2 }); vec.push_back({ arr[i].second,i * 2 + 1 }); sz[i * 2] = sz[i * 2 + 1] = 1; par[i * 2] = i * 2; par[i * 2 + 1] = i * 2 + 1; } sort(vec.begin(), vec.end()); merge(0, vec[1].second); for (int i = 1; i <= n; i++) { int le = arr[i].first; int ri = arr[i].second; merge(i * 2, lower_bound(vec.begin(), vec.end(), make_pair(ri + 1, 0))->second); merge(i * 2 + 1, lower_bound(vec.begin(), vec.end(), make_pair(le + 1, 0))->second); } priority_queue<int> pq; for (int i = 0; i < (n + 1) * 2; i++) { if (i == find(i) && find(i) != find(0))pq.push(sz[find(i)]); } int ans = sz[find(0)] + m * 2; while (!pq.empty() && m--) { ans += pq.top(); pq.pop(); } printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 624 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 648 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 748 KB | Output is correct |
2 | Correct | 14 ms | 1132 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 1132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 1256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 1640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 135 ms | 5972 KB | Output is correct |
2 | Correct | 367 ms | 15028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 235 ms | 15028 KB | Output is correct |
2 | Incorrect | 682 ms | 19268 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1018 ms | 29504 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1084 ms | 35192 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1086 ms | 39996 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |