oj.uz

답안 #740272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740272 2023-05-12T09:11:46 Z Ahmed57 Teleporters (IOI08_teleporters) C++17
100 / 100
 479 ms 56312 KB 
#include <bits/stdc++.h>

using namespace std;
int tele[2000005];
int le[2000005];
bool vis[2000005];
int ans = 0;bool ss = 0;
void dfs(int i){
    ans++;vis[i] = 1;
    if(tele[i]==0){ss = 1;return ;}
    if(!vis[tele[i]])dfs(tele[i]);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    priority_queue<int> q;
    vector<pair<int,int>> v;
    vector<pair<int,int>> te;
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        v.push_back({a,b});v.push_back({b,a});
    }
    sort(v.begin(),v.end());
    for(int i = 0;i<v.size();i++){
        le[v[i].first] = i+1;
    }
    for(int i = 0;i<v.size();i++){
        tele[i+1] = le[v[i].second]+1;
    }
    int org = 0;
    for(int i = 1;i<=2*n+1;i++){
        if(!vis[i]){
            ss = 0;ans = 0;
            dfs(i);
            if(ss){
                org = ans-1;
            }else{
                q.push(ans);
            }
        }
    }
    while(m--){
        if(q.size()==0){
            org++;q.push(1);
        }else{
            org+=q.top()+2;q.pop();
        }
    }
    cout<<org<<endl;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
teleporters.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 5 ms 996 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 5 ms 1368 KB Output is correct
3 Correct 14 ms 1752 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 984 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1240 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 7648 KB Output is correct
2 Correct 141 ms 19572 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 14384 KB Output is correct
2 Correct 279 ms 27052 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 36760 KB Output is correct
2 Correct 372 ms 42120 KB Output is correct
3 Correct 359 ms 46712 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 417 ms 46724 KB Output is correct
2 Correct 402 ms 50072 KB Output is correct
3 Correct 383 ms 47880 KB Output is correct
4 Correct 375 ms 48228 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 54744 KB Output is correct
2 Correct 479 ms 55120 KB Output is correct
3 Correct 357 ms 56312 KB Output is correct
4 Correct 457 ms 56164 KB Output is correct