# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
583303 | 2022-06-25T08:23:01 Z | hibiki | Teleporters (IOI08_teleporters) | C++11 | 418 ms | 23580 KB |
#include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second #define all(x) x.begin(),x.end() int n,m; pair<int,int> go[2000005]; bool pass[2000005]; int main() { scanf("%d %d",&n,&m); for(int i = 0; i < 2000005; i++) go[i] = {i + 1, 0}; for(int i = 0; i < n; i++) { int a,b; scanf("%d %d",&a,&b); go[a] = {b + 1, 1}; go[b] = {a + 1, 1}; } int ans = 0; priority_queue<int> pq; pass[2000005 - 1] = true; for(int i = 0; i < 2000005; i++) { if(pass[i]) continue; int cnt = 0, nw = i; while(!pass[nw]) { pass[nw] = true; cnt += go[nw].s; nw = go[nw].f; } if(i == 0) ans += cnt; else { // printf("%d %d\n",i,cnt); pq.push(cnt); } } while(m > 0 && !pq.empty()) { ans += pq.top() + 2; pq.pop(); m--; } ans += (m / 2) * 4 + (m % 2); printf("%d\n",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 17900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 17848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 17872 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 17896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 17876 KB | Output is correct |
2 | Correct | 20 ms | 17880 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17888 KB | Output is correct |
2 | Correct | 20 ms | 17876 KB | Output is correct |
3 | Correct | 24 ms | 17828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17812 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 17896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 18280 KB | Output is correct |
2 | Correct | 155 ms | 19916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 88 ms | 18500 KB | Output is correct |
2 | Correct | 187 ms | 18528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 313 ms | 20056 KB | Output is correct |
2 | Correct | 269 ms | 20032 KB | Output is correct |
3 | Correct | 336 ms | 23580 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 369 ms | 20060 KB | Output is correct |
2 | Correct | 366 ms | 20028 KB | Output is correct |
3 | Correct | 356 ms | 19236 KB | Output is correct |
4 | Correct | 409 ms | 19200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 418 ms | 22072 KB | Output is correct |
2 | Correct | 407 ms | 23544 KB | Output is correct |
3 | Correct | 304 ms | 23296 KB | Output is correct |
4 | Correct | 395 ms | 23524 KB | Output is correct |