# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
915873 | 2024-01-24T20:12:49 Z | Matjaz | Teleporters (IOI08_teleporters) | C++14 | 991 ms | 65536 KB |
// // IOI2008Teleporters.cpp // // // Created by Matjaz Leonardis on 24/01/2024. // #include <iostream> #include <vector> #include <algorithm> #include <assert.h> using namespace std; int N,M; int main(){ cin >> N >> M; vector<pair<int,int> > X; vector<int> next(4*N, -1); for (int i=0;i<N;i++){ int W,E; cin >> W >> E; X.push_back(make_pair(W, 4 * i)); X.push_back(make_pair(W, 4 * i + 1)); X.push_back(make_pair(E, 4 * i + 2)); X.push_back(make_pair(E, 4 * i + 3)); next[4 * i] = 4 * i + 3; next[4 * i + 2] = 4 * i + 1; } sort(X.begin(), X.end()); for (int i=0;i<X.size() - 1; i++){ //cout << i << " " << X[i].first << " " << X[i].second << endl; if (next[X[i].second] == -1) next[X[i].second] = X[i + 1].second; } int jumps = 0; vector<int> cycle; vector<bool> visited(4 * N, false); for (int i=0;i<X.size();i++){ //cout << next[X[i].second] << endl; //cout << i << " " << X[i].first << " " << X[i].second << endl; if (visited[X[i].second]) continue; int current = X[i].second; int l = 0; visited[X[i].second] = true; //cout << current << " "; while (next[current] != X[i].second && next[current] != -1){ l++; current = next[current]; visited[current] = true; //cout << current << " "; } //cout << endl; assert(l % 2 == 1); //cout << "l:" << l << endl; if (i == 0){ jumps += (l + 1) / 2; } else cycle.push_back(l); } sort(cycle.rbegin(), cycle.rend()); for (int i=0;i<M;i++){ if (i >= cycle.size()) break; else jumps += (cycle[i] + 1) / 2 + 2; //if (i < cycle.size()) cout << cycle[i] << endl; } if (M > cycle.size()){ M -= cycle.size(); if (M % 2 == 0) jumps += 2 * M; if (M % 2 == 1) jumps += 2 * M - 1; } cout << jumps << endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 412 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 856 KB | Output is correct |
2 | Correct | 7 ms | 1240 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 604 KB | Output is correct |
2 | Correct | 9 ms | 1240 KB | Output is correct |
3 | Correct | 21 ms | 2256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 1236 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 1748 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 97 ms | 8392 KB | Output is correct |
2 | Correct | 254 ms | 23404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 168 ms | 12784 KB | Output is correct |
2 | Correct | 373 ms | 25328 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 532 ms | 43944 KB | Output is correct |
2 | Correct | 679 ms | 54832 KB | Output is correct |
3 | Correct | 734 ms | 59284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 857 ms | 58956 KB | Output is correct |
2 | Correct | 880 ms | 64048 KB | Output is correct |
3 | Correct | 866 ms | 63500 KB | Output is correct |
4 | Correct | 879 ms | 63164 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 951 ms | 65536 KB | Output is correct |
2 | Correct | 977 ms | 65536 KB | Output is correct |
3 | Correct | 671 ms | 65536 KB | Output is correct |
4 | Correct | 991 ms | 65536 KB | Output is correct |