# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
537094 | 2022-03-14T12:59:56 Z | ToroTN | Teleporters (IOI08_teleporters) | C++14 | 555 ms | 56120 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,kmp; 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(); //printf("%d\n",u); 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; } } } //printf("%d\n",ans); for(int i=1;i<=m;i++) { if(pq.size()!=0) { //printf("%d ",pq.top()); ans+=pq.top(); pq.pop(); ans+=2; }else { if(kmp%2==0) { ans+=1; }else { ans+=3; } ++kmp; } } //printf("\n"); printf("%d\n",ans); } /* 3 1 10 11 1 4 2 3 */ /* 3 3 14 18 12 15 10 20 */
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 | 4 ms | 8112 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 | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8164 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 | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8324 KB | Output is correct |
2 | Correct | 8 ms | 8660 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8276 KB | Output is correct |
2 | Correct | 8 ms | 9076 KB | Output is correct |
3 | Correct | 17 ms | 9552 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 8784 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 13508 KB | Output is correct |
2 | Correct | 161 ms | 22548 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 18740 KB | Output is correct |
2 | Correct | 238 ms | 27444 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 332 ms | 34312 KB | Output is correct |
2 | Correct | 393 ms | 37540 KB | Output is correct |
3 | Correct | 443 ms | 41148 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 466 ms | 40036 KB | Output is correct |
2 | Correct | 518 ms | 56120 KB | Output is correct |
3 | Correct | 511 ms | 53668 KB | Output is correct |
4 | Correct | 514 ms | 54168 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 555 ms | 45912 KB | Output is correct |
2 | Correct | 547 ms | 46264 KB | Output is correct |
3 | Correct | 409 ms | 47464 KB | Output is correct |
4 | Correct | 484 ms | 47424 KB | Output is correct |