# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
98866 | 2019-02-27T02:44:29 Z | shoemakerjo | Teleporters (IOI08_teleporters) | C++14 | 810 ms | 45560 KB |
#include <bits/stdc++.h> using namespace std; int N, M; const int maxn = 2000010; int aft[maxn]; int bef[maxn]; bool isin[maxn]; bool vis[maxn]; int a[maxn], b[maxn]; int previn[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); fill(aft, aft+maxn, -1); cin >> N >> M; for (int i = 0; i < N; i++) { cin >> a[i] >> b[i]; isin[a[i]] = true; isin[b[i]] = true; } int cp = 0; for (int i = 1; i < maxn; i++) { if (isin[i]) { previn[i] = cp; cp = i; } } for (int i = 0; i < N; i++) { aft[previn[a[i]]] = b[i]; bef[b[i]] = previn[a[i]]; // cout << "thing: " << previn[a[i]] << " - " << b[i] << // " :: " << a[i] << endl; aft[previn[b[i]]] = a[i]; bef[a[i]] = previn[b[i]]; } vector<int> cyclen; int clen = 0; for (int i = 0; i < maxn; i++) { if (!isin[i] || vis[i]) continue; int cv = 0; int u = i; bool ip = false; // cout << " path: "; while (!vis[u]) { // cout << u << " "; cv++; vis[u] = true; u = aft[u]; if (u == -1) { ip = true; clen = cv; break; } } // cout << u << endl; if (!ip) cyclen.push_back(cv); } sort(cyclen.begin(), cyclen.end()); reverse(cyclen.begin(), cyclen.end()); // cout << "this: " << clen << endl; for (int i = 0; i < cyclen.size(); i++) { if (M == 0) break; M--; clen += cyclen[i] + 2; } if (M) { int d2 = M/2; if (M %2 == 1) clen++; clen += d2 * 4; } cout << clen << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 8192 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8256 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8192 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 8164 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 8320 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 8260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8576 KB | Output is correct |
2 | Correct | 20 ms | 8952 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8524 KB | Output is correct |
2 | Correct | 20 ms | 9572 KB | Output is correct |
3 | Correct | 22 ms | 9336 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 8704 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 8960 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 16248 KB | Output is correct |
2 | Correct | 272 ms | 31680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 156 ms | 25464 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 494 ms | 40244 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 659 ms | 42300 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 810 ms | 45560 KB | Output is correct |
2 | Incorrect | 767 ms | 45392 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |