oj.uz

답안 #274625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
274625 2020-08-19T13:19:07 Z evpipis Teleporters (IOI08_teleporters) C++11
100 / 100
 759 ms 54376 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 2e6+5;
int vis[len], nex[len];
vector<ii> vec;
priority_queue<int> pq;

int dfs(int u){
    vis[u] = 1;

    int ans = 1;
    if (!vis[nex[u]])
        ans += dfs(nex[u]);

    return ans;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vec.pb(mp(a, 2*i));
        vec.pb(mp(b, 2*i+1));
    }

    sort(vec.begin(), vec.end());

    for (int i = 0; i < 2*n-1; i++)
        nex[vec[i].se] = vec[i+1].se^1;

    int st = 2*n;
    nex[st] = vec[0].se^1;
    nex[vec[2*n-1].se] = st;
    vis[st] = 1;

    int ans = dfs(nex[st]);
    for (int i = 0; i < 2*n; i++)
        if (!vis[i])
            pq.push(dfs(i));

    while (m--){
        if (pq.empty())
            ans++, pq.push(1);
        else
            ans += 2+pq.top(), pq.pop();
    }

    printf("%d\n", ans);
    return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
teleporters.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 9 ms 1020 KB Output is correct
3 Correct 16 ms 1784 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 6532 KB Output is correct
2 Correct 201 ms 15100 KB Output is correct

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 32700 KB Output is correct
2 Correct 527 ms 38716 KB Output is correct
3 Correct 622 ms 45120 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 666 ms 44092 KB Output is correct
2 Correct 687 ms 47932 KB Output is correct
3 Correct 672 ms 45884 KB Output is correct
4 Correct 676 ms 46412 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 759 ms 52956 KB Output is correct
2 Correct 743 ms 53052 KB Output is correct
3 Correct 503 ms 54376 KB Output is correct
4 Correct 721 ms 54204 KB Output is correct