# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
537069 | 2022-03-14T11:13:02 Z | ToroTN | Teleporters (IOI08_teleporters) | C++14 | 647 ms | 62120 KB |
#include<bits/stdc++.h> using namespace std; int n,m,a[2000005],x[1000005],y[1000005],go[2000005],hsh[2000005],d[2000005],node,u,cnt,ans; vector<int> v; queue<int> q; priority_queue<int> pq; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]); v.push_back(x[i]); v.push_back(y[i]); } sort(v.begin(),v.end()); for(int i=0;i<v.size();i++) { hsh[v[i]]=i+1; } for(int i=1;i<=n;i++) { go[hsh[x[i]]]=hsh[y[i]]; go[hsh[y[i]]]=hsh[x[i]]; } memset(d,-1,sizeof d); d[2*n+1]=0; for(int i=1;i<=2*n;i++) { if(d[i]==-1) { q.push(i); d[i]=0; cnt=0; //printf("node=%d\n",i); while(!q.empty()) { u=q.front(); q.pop(); ++cnt; u=go[u]; u+=1; if(d[u]==-1) { d[u]=0; q.push(u); }else { while(!q.empty()) { q.pop(); } } } //printf("%d\n",cnt); pq.push(cnt); } } for(int i=1;i<=m+1;i++) { if(pq.size()!=0) { ans+=pq.top(); pq.pop(); } if(i!=1) { ans+=2; } } printf("%d\n",ans); } /* 3 1 10 11 1 4 2 3 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 8148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8120 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 8272 KB | Output is correct |
2 | Correct | 8 ms | 8852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 8304 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 8756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 15156 KB | Output is correct |
2 | Correct | 173 ms | 26916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 21656 KB | Output is correct |
2 | Incorrect | 271 ms | 34016 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 378 ms | 43360 KB | Output is correct |
2 | Correct | 407 ms | 48476 KB | Output is correct |
3 | Correct | 500 ms | 52920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 515 ms | 52852 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 647 ms | 60588 KB | Output is correct |
2 | Correct | 605 ms | 60832 KB | Output is correct |
3 | Correct | 406 ms | 62120 KB | Output is correct |
4 | Correct | 551 ms | 61988 KB | Output is correct |