oj.uz

답안 #221784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221784 2020-04-11T05:22:03 Z anonymous Teleporters (IOI08_teleporters) C++14
100 / 100
 784 ms 56256 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define MAXN 1000005
#define fi first
#define se second
using namespace std;
int N, M, Ans, TP[MAXN][2], Pos[2*MAXN];
bool vis[2*MAXN]; //just visited endpoint [i]
vector <int> Cyc;
vector <pair<int,int> > L;

int main() {
    //freopen("tpin.txt","r",stdin);
    scanf("%d\n%d",&N,&M);
    for (int i=1; i<=N; i++) {
        scanf("%d %d",&TP[i][0], &TP[i][1]);
        L.push_back({TP[i][0], i});
        L.push_back({TP[i][1], i});
    }
    L.push_back({0,0});
    sort(L.begin(), L.end());
    for (int i=0; i<L.size(); i++) {
        Pos[L[i].fi] = i;
    }
    for (int i=0; i<L.size(); i++) {
        if (vis[i]) {continue;}
        int sz = 0, cur = i;
        while (!vis[cur]) {
            vis[cur] = true;
            if (cur == L.size()-1) {
                Ans += sz;
                break;
            }
            sz += 1;
            if (L[cur+1].fi == TP[L[cur+1].se][0]) {
                cur = Pos[TP[L[cur+1].se][1]];
            } else {
                cur = Pos[TP[L[cur+1].se][0]];
            }
        }
        if (i) {Cyc.push_back(sz);}
    }
    sort(Cyc.begin(), Cyc.end());
    while (M && Cyc.size()) {
        Ans += Cyc.back() + 2;
        M -=1;
        Cyc.pop_back();
    }
    if (M%2) {Ans += 1;}
    Ans += 4*(M/2);
    printf("%d\n", Ans);
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<L.size(); i++) {
                   ~^~~~~~~~~
teleporters.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<L.size(); i++) {
                   ~^~~~~~~~~
teleporters.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (cur == L.size()-1) {
                 ~~~~^~~~~~~~~~~~~
teleporters.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n%d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~~
teleporters.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&TP[i][0], &TP[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 15 ms 1404 KB Output is correct
3 Correct 20 ms 1936 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 7652 KB Output is correct
2 Correct 242 ms 19772 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 14428 KB Output is correct
2 Correct 345 ms 27012 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 442 ms 36796 KB Output is correct
2 Correct 551 ms 42172 KB Output is correct
3 Correct 545 ms 46652 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 739 ms 46844 KB Output is correct
2 Correct 784 ms 50364 KB Output is correct
3 Correct 634 ms 47908 KB Output is correct
4 Correct 655 ms 48444 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 759 ms 54716 KB Output is correct
2 Correct 775 ms 55164 KB Output is correct
3 Correct 455 ms 56256 KB Output is correct
4 Correct 679 ms 56252 KB Output is correct