# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56747 | 2018-07-12T11:32:04 Z | win11905 | Teleporters (IOI08_teleporters) | C++11 | 880 ms | 66560 KB |
#include <bits/stdc++.h> #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 2e6+5; int n, m, V[N], val[N], neibour[N], Com[N], psz, pz1; bool Check[N]; int main() { scanf("%d %d", &n, &m); for(int i = 0, u, v; i < n; ++i) { scanf("%d %d", &u, &v); neibour[u] = v, neibour[v] = u; V[u]++, V[v]++; } for(int i = 1; i < N; ++i) { V[i] += V[i-1]; if(V[i] != V[i-1]) Com[pz1++] = i; } int cnt = 0, p = 0; Check[0] = true; while(p != (n<<1)) Check[p = V[neibour[Com[p]]]] = true, cnt++; for(int i = 1; i <= (n<<1); ++i) if(!Check[i]) { int u = i, sz = 0; Check[u] = true; do Check[u = V[neibour[Com[u]]]] = true, sz++; while(u != i); val[++psz] = sz; val[psz] += val[psz-1]; } cnt += val[min(psz, m)] + 2 * min(psz, m); if(m > psz) m -= psz, cnt += ((m>>1)<<2) + (m & 1); printf("%d\n", cnt); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8360 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 8384 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8436 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 8444 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 8448 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 8452 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 8588 KB | Output is correct |
2 | Incorrect | 23 ms | 8876 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 8876 KB | Output is correct |
2 | Incorrect | 28 ms | 9580 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 9580 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 9580 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 130 ms | 14356 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 242 ms | 21100 KB | Output is correct |
2 | Correct | 485 ms | 33244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 587 ms | 45012 KB | Output is correct |
2 | Incorrect | 591 ms | 57564 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 815 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 880 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 | Halted | 0 ms | 0 KB | - |