# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
915852 | 2024-01-24T19:14:40 Z | Matjaz | Teleporters (IOI08_teleporters) | C++14 | 823 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(4*N); 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++){ 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++){ if (visited[X[i].second]) continue; int current = X[i].second; int l = 0; visited[X[i].second] = true; while (next[current] != X[i].second && next[current] != -1){ l++; current = next[current]; visited[current] = true; } assert(l % 2 == 1); 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 604 KB | Output is correct |
2 | Correct | 11 ms | 1364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 856 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 1868 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 117 ms | 12484 KB | Output is correct |
2 | Correct | 306 ms | 29224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 191 ms | 20832 KB | Output is correct |
2 | Incorrect | 453 ms | 43188 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 657 ms | 62044 KB | Output is correct |
2 | Correct | 777 ms | 65536 KB | Output is correct |
3 | Runtime error | 823 ms | 65536 KB | Execution killed with signal 9 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 20 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 19 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |