# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
54169 | 2018-07-02T15:05:44 Z | 0^0(#1448) | Teleporters (IOI08_teleporters) | C++11 | 848 ms | 55744 KB |
#include <bits/stdc++.h> using namespace std; int n, m; pair<int, int> arr[1000005]; vector<pair<int, int> > vec; pair<int, int> nidx[1000005]; int par[2000005]; int sz[2000005]; int find(int x) { if (par[x] == x)return x; return par[x] = find(par[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()); for (int i = 1; i + 1 < vec.size(); i++) { int idx = vec[i].second; if (idx & 1) nidx[idx / 2].second = vec[i + 1].second; else nidx[idx / 2].first = vec[i + 1].second; } 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, nidx[i].second); merge(i * 2 + 1, nidx[i].first); } vector<int> t; int p = find(0); for (int i = 0; i < (n + 1) * 2; i++) { int f = find(i); if (i == f && f != p)t.push_back(sz[f]); } sort(t.begin(), t.end()); int ans = sz[p] + m * 2; for (int i = 0; i < t.size() && i < m; i++) ans += t[t.size() - 1 - i]; printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 248 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 356 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 436 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 508 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 712 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 712 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 748 KB | Output is correct |
2 | Correct | 8 ms | 1132 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1640 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 93 ms | 7000 KB | Output is correct |
2 | Correct | 203 ms | 15676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 143 ms | 15676 KB | Output is correct |
2 | Incorrect | 316 ms | 22768 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 449 ms | 33584 KB | Output is correct |
2 | Correct | 553 ms | 39804 KB | Output is correct |
3 | Correct | 572 ms | 46512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 735 ms | 46512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 781 ms | 54180 KB | Output is correct |
2 | Correct | 842 ms | 54576 KB | Output is correct |
3 | Correct | 482 ms | 55636 KB | Output is correct |
4 | Correct | 848 ms | 55744 KB | Output is correct |