Submission #221784

#	Time	Username	Problem	Language	Result	Execution time	Memory
221784		anonymous	Teleporters (IOI08_teleporters)	C++14	100 / 100	784 ms	56256 KiB

teleporters

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5