# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
649240 | 2022-10-09T17:03:17 Z | Spade1 | Teleporters (IOI08_teleporters) | C++14 | 432 ms | 40568 KB |
#include<bits/stdc++.h> #define pii pair<int, int> #define pll pair<long long, long long> #define ll long long #define ld long double #define st first #define nd second #define pb push_back #define INF INT_MAX using namespace std; const int N = 2e6 + 10; int to[N]; int cnt[N], srt[N]; bool vis[N]; vector<pii> tp; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; cnt[a]++; cnt[b]++; tp.pb({a, b}); } for (int i = 1; i < N; ++i) { cnt[i] += cnt[i-1]; } for (auto [a, b] : tp) { to[cnt[a-1]] = cnt[b]; to[cnt[b-1]] = cnt[a]; } int ans = 0; for (int i = 0; i < 2*n; ++i) { if (vis[i]) continue; int cntt = 0; while (!vis[i]) { vis[i] = 1; cntt++; i = to[i]; } if (i == 0) { ans = cntt; } else srt[cntt]++; } for (int i = N-1; i > 0; --i) { if (srt[i] <= m) { m -= srt[i]; ans += (srt[i]*i) + 2*srt[i]; } else { ans += m*i + 2*m; m = 0; break; } } if (m > 0) { if (m&1) { ans += 2*(m-1)+1; } else { ans += 2*m; } } cout << ans-1 << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8180 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8180 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8100 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8124 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8224 KB | Output is correct |
2 | Correct | 13 ms | 8528 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8276 KB | Output is correct |
2 | Correct | 19 ms | 8636 KB | Output is correct |
3 | Correct | 19 ms | 9176 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 10416 KB | Output is correct |
2 | Correct | 112 ms | 13596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 12024 KB | Output is correct |
2 | Correct | 187 ms | 22864 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 242 ms | 19468 KB | Output is correct |
2 | Correct | 307 ms | 32476 KB | Output is correct |
3 | Correct | 335 ms | 34488 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 360 ms | 23712 KB | Output is correct |
2 | Correct | 422 ms | 38772 KB | Output is correct |
3 | Correct | 350 ms | 40040 KB | Output is correct |
4 | Correct | 432 ms | 40516 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 382 ms | 25916 KB | Output is correct |
2 | Correct | 390 ms | 40568 KB | Output is correct |
3 | Correct | 226 ms | 40432 KB | Output is correct |
4 | Correct | 369 ms | 40392 KB | Output is correct |