# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
537085 | 2022-03-14T12:35:42 Z | ToroTN | Teleporters (IOI08_teleporters) | C++14 | 586 ms | 47556 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; } printf("%d\n",ans); } /* 3 1 10 11 1 4 2 3 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 8096 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 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 | 3 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8276 KB | Output is correct |
2 | Correct | 7 ms | 8684 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 | 8 ms | 8660 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8772 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 13512 KB | Output is correct |
2 | Correct | 150 ms | 22608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 18812 KB | Output is correct |
2 | Incorrect | 235 ms | 27580 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 333 ms | 34324 KB | Output is correct |
2 | Correct | 371 ms | 37676 KB | Output is correct |
3 | Correct | 412 ms | 41068 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 473 ms | 40036 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 586 ms | 45988 KB | Output is correct |
2 | Correct | 538 ms | 46372 KB | Output is correct |
3 | Correct | 372 ms | 47556 KB | Output is correct |
4 | Correct | 454 ms | 47524 KB | Output is correct |