# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56768 | 2018-07-12T14:30:45 Z | win11905 | Teleporters (IOI08_teleporters) | C++11 | 803 ms | 55340 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, psz, pz1; bool Check[N]; int main() { vector<int> V(N), val(N), neibour(N), Com(N); 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; } sort(val.begin()+1, val.begin() + psz + 1, greater<int>()); for(int i = 1; i <= psz; ++i) val[i] += val[i-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 | 35 ms | 31608 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 31848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 31900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 31900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 31900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 31912 KB | Output is correct |
2 | Correct | 41 ms | 31912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 31912 KB | Output is correct |
2 | Correct | 51 ms | 31944 KB | Output is correct |
3 | Correct | 44 ms | 31944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 31944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 40 ms | 31944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 32132 KB | Output is correct |
2 | Correct | 270 ms | 32460 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 190 ms | 32460 KB | Output is correct |
2 | Correct | 391 ms | 32876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 470 ms | 33276 KB | Output is correct |
2 | Correct | 513 ms | 33532 KB | Output is correct |
3 | Correct | 410 ms | 33532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 678 ms | 33620 KB | Output is correct |
2 | Correct | 803 ms | 40524 KB | Output is correct |
3 | Correct | 579 ms | 40576 KB | Output is correct |
4 | Correct | 633 ms | 40604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 705 ms | 40604 KB | Output is correct |
2 | Correct | 600 ms | 40604 KB | Output is correct |
3 | Correct | 344 ms | 40604 KB | Output is correct |
4 | Correct | 501 ms | 55340 KB | Output is correct |