# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
537084 | 2022-03-14T12:35:03 Z | ToroTN | Teleporters (IOI08_teleporters) | C++14 | 559 ms | 46036 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); if(i!=1) { pq.push(cnt); }else { ans=cnt; } } } for(int i=1;i<=m;i++) { if(pq.size()!=0) { ans+=pq.top(); ans+=2; pq.pop(); }else { ans+=3; } } printf("%d\n",ans); } /* 3 1 10 11 1 4 2 3 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 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 | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 8148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 8148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 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 | 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 | 8148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8168 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8276 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 8372 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 8600 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 8712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 13452 KB | Output is correct |
2 | Correct | 179 ms | 22528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 113 ms | 18716 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 344 ms | 34312 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 535 ms | 40180 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 559 ms | 46036 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |