# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
197917 | 2020-01-24T08:39:17 Z | SamAnd | Teleporters (IOI08_teleporters) | C++17 | 881 ms | 48416 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2000006; struct ban { int x, i; ban(){} ban(int x, int i) { this->x = x; this->i = i; } }; bool operator<(const ban& a, const ban& b) { return a.x < b.x; } int u[N]; void mysort(vector<int>& v) { memset(u, 0, sizeof u); for (int i = 0; i < v.size(); ++i) u[v[i]]++; v.clear(); for (int i = 0; i < N; ++i) { for (int j = 0; j < u[i]; ++j) v.push_back(i); } } int n, m; pair<int, int> b[N]; vector<int> v; int a[N]; bool c[N]; int q; void dfs(int x) { c[x] = true; ++q; int h = a[x]; if (!c[h]) dfs(h); } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); #endif // SOMETHING scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d%d", &b[i].first, &b[i].second); v.push_back(b[i].first); v.push_back(b[i].second); } mysort(v); for (int i = 1; i <= n; ++i) { b[i].first = lower_bound(v.begin(), v.end(), b[i].first) - v.begin() + 1; b[i].second = lower_bound(v.begin(), v.end(), b[i].second) - v.begin() + 1; } for (int i = 1; i <= n; ++i) { a[b[i].first - 1] = (b[i].second); a[b[i].second - 1] = (b[i].first); } int ans = 0; q = 0; dfs(0); ans += (q - 1); v.clear(); for (int i = 1; i <= n * 2; ++i) { if (!c[i]) { q = 0; dfs(i); v.push_back(q); } } mysort(v); reverse(v.begin(), v.end()); for (int i = 0; i < min((int)v.size(), m); ++i) { ans += (v[i] + 2); } m -= v.size(); for (int i = 0; i < m; ++i) { if (i % 2 == 0) ans += 1; else ans += 3; } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8188 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8084 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8156 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8156 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 8312 KB | Output is correct |
2 | Correct | 20 ms | 8568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 8372 KB | Output is correct |
2 | Correct | 21 ms | 8568 KB | Output is correct |
3 | Correct | 30 ms | 9076 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 8568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 8692 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 11456 KB | Output is correct |
2 | Correct | 258 ms | 15952 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 171 ms | 13792 KB | Output is correct |
2 | Correct | 374 ms | 19728 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 505 ms | 24176 KB | Output is correct |
2 | Correct | 622 ms | 27476 KB | Output is correct |
3 | Correct | 649 ms | 29252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 786 ms | 30780 KB | Output is correct |
2 | Correct | 850 ms | 32628 KB | Output is correct |
3 | Correct | 814 ms | 47852 KB | Output is correct |
4 | Correct | 811 ms | 48384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 881 ms | 33756 KB | Output is correct |
2 | Correct | 880 ms | 48372 KB | Output is correct |
3 | Correct | 456 ms | 48404 KB | Output is correct |
4 | Correct | 831 ms | 48416 KB | Output is correct |