# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95130 | 2019-01-27T14:37:26 Z | Retro3014 | Teleporters (IOI08_teleporters) | C++17 | 745 ms | 66560 KB |
#include <iostream> #include <algorithm> #include <vector> #include <stdio.h> #define MAX_X 2000000 using namespace std; typedef long long ll; int N, M; struct S{ S(int x, int y) : x(x), y(y) {} int x, y; }; vector<S> v; int g[MAX_X+1]; vector<int> v2; int l[MAX_X+1], r[MAX_X+1]; bool vst[MAX_X+1]; vector<ll> cycle; ll ans; void dfs(int x, ll y){ if(vst[x]){ cycle.push_back(y); return; } vst[x] = true; if(x==v2.size()-1){ ans+=y; return; } dfs(r[x], y+1); } int main(){ scanf("%d%d", &N, &M); for(int i=0; i<N; i++){ int a, b; scanf("%d%d", &a, &b); v.push_back({a, b}); v2.push_back(a); v2.push_back(b); } v2.push_back(0); sort(v2.begin(), v2.end()); for(int i=0; i<v2.size(); i++){ g[v2[i]] = i; } for(int i=0; i<v.size(); i++){ S now = v[i]; r[g[now.x]-1] = g[now.y]; l[g[now.x]] = g[now.y]-1; r[g[now.y]-1] = g[now.x]; l[g[now.y]] = g[now.x]-1; } for(int i=0; i<v2.size(); i++){ if(vst[i]) continue; dfs(i, 0); } /*printf("%d\n", ans); for(int i=0; i<cycle.size(); i++){ printf("%d\n", cycle[i]); }*/ sort(cycle.begin(), cycle.end()); while(M--){ if(cycle.empty()){ cycle.push_back(1); ans++; }else{ ans+=2+cycle.back(); cycle.pop_back(); } } printf("%lld", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 632 KB | Output is correct |
2 | Correct | 6 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 760 KB | Output is correct |
2 | Correct | 7 ms | 1660 KB | Output is correct |
3 | Correct | 14 ms | 4084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 2036 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 12004 KB | Output is correct |
2 | Correct | 203 ms | 27772 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 19540 KB | Output is correct |
2 | Correct | 282 ms | 43080 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 432 ms | 49488 KB | Output is correct |
2 | Correct | 523 ms | 54160 KB | Output is correct |
3 | Runtime error | 534 ms | 66560 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 676 ms | 61160 KB | Output is correct |
2 | Runtime error | 698 ms | 66560 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 745 ms | 66560 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |