# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
118711 | 2019-06-19T13:24:34 Z | eriksuenderhauf | Teleporters (IOI08_teleporters) | C++11 | 487 ms | 20712 KB |
#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 2e6 + 5; const double eps = 1e-9; int nx[MAXN], vis[MAXN]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0 ; i < MAXN; i++) nx[i] = i + 1; vis[MAXN - 1] = 1; for (int i = 0; i < n; i++) { int u, v; scanf("%d %d", &u, &v); nx[u - 1] = v; nx[v - 1] = u; } int ans = -1; priority_queue<int> pq; for (int i = 0; i < MAXN; i++) { if (vis[i]) continue; int cur = i, cnt = 0; while (!vis[cur]) { vis[cur] = 1; if (nx[cur] != cur + 1) cnt++; cur = nx[cur]; } if (ans == -1) ans = cnt; else pq.push(cnt); } while (!pq.empty() && m > 0) { m--; ans += pq.top() + 2; pq.pop(); } ans += (m + 1) / 2 + (m / 2) * 3; pri(ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 15952 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 15992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 15992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 15932 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 16040 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 16000 KB | Output is correct |
2 | Correct | 26 ms | 16120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 16000 KB | Output is correct |
2 | Correct | 25 ms | 16120 KB | Output is correct |
3 | Correct | 28 ms | 16120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 16120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 16248 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 71 ms | 16580 KB | Output is correct |
2 | Correct | 173 ms | 16984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 121 ms | 17020 KB | Output is correct |
2 | Correct | 230 ms | 16976 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 302 ms | 18540 KB | Output is correct |
2 | Correct | 342 ms | 18540 KB | Output is correct |
3 | Correct | 350 ms | 20584 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 432 ms | 18508 KB | Output is correct |
2 | Correct | 435 ms | 18540 KB | Output is correct |
3 | Correct | 379 ms | 16376 KB | Output is correct |
4 | Correct | 392 ms | 16376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 463 ms | 20580 KB | Output is correct |
2 | Correct | 487 ms | 20712 KB | Output is correct |
3 | Correct | 399 ms | 20320 KB | Output is correct |
4 | Correct | 406 ms | 20584 KB | Output is correct |