# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95028 | 2019-01-27T04:17:09 Z | Retro3014 | Teleporters (IOI08_teleporters) | C++17 | 720 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(2); }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 | Incorrect | 2 ms | 376 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't 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 | 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 | 1144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 764 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 1652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 10340 KB | Output is correct |
2 | Correct | 166 ms | 23472 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 16644 KB | Output is correct |
2 | Incorrect | 316 ms | 36516 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 386 ms | 40672 KB | Output is correct |
2 | Correct | 453 ms | 46512 KB | Output is correct |
3 | Runtime error | 523 ms | 66560 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 672 ms | 54060 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 720 ms | 66560 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |