# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
537086 | 2022-03-14T12:37:30 Z | ToroTN | Teleporters (IOI08_teleporters) | C++14 | 564 ms | 47484 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(); pq.pop(); ans+=2; }else { ans+=2; } } printf("%d\n",ans); } /* 3 1 10 11 1 4 2 3 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8080 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 8148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 8148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8276 KB | Output is correct |
2 | Correct | 8 ms | 8668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8276 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8624 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8712 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 13412 KB | Output is correct |
2 | Correct | 164 ms | 22504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 115 ms | 18816 KB | Output is correct |
2 | Incorrect | 231 ms | 27376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 361 ms | 34276 KB | Output is correct |
2 | Correct | 379 ms | 37580 KB | Output is correct |
3 | Correct | 475 ms | 41116 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 468 ms | 40048 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 552 ms | 46044 KB | Output is correct |
2 | Correct | 564 ms | 46260 KB | Output is correct |
3 | Correct | 415 ms | 47428 KB | Output is correct |
4 | Correct | 443 ms | 47484 KB | Output is correct |