Submission #724826

#	Time	Username	Problem	Language	Result	Execution time	Memory
724826		khanhdz06	Teleporters (IOI08_teleporters)	C++17	100 / 100	383 ms	33844 KiB

teleporters

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m, tel[2000002];
bool vis[2000002];
priority_queue<ll> pq;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    for(int i=0; i<2000002; i++){
        tel[i] = i+1;
    }
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        ll l, r; cin >> l >> r;
        tel[l-1] = r;
        tel[r-1] = l;
    }
    ll len = -1;
    vis[2000002] = 1;
    for(int i=0; i<2000002; i++){
        if(!vis[i]){
            ll pos = i, ret = 0;
            while(!vis[pos]){
                vis[pos] = 1;
                if(tel[pos] != pos+1) ret++;
                pos = tel[pos];
            }
            if(len==-1) len = ret;
            else pq.push(ret);
        }
    }
    while(!pq.empty() && m--){
        len += pq.top()+2;
        pq.pop();
    }
    len += (m+1)/2 + (m/2)*3;
    cout << len;
}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:23:16: warning: array subscript 2000002 is above array bounds of 'bool [2000002]' [-Warray-bounds]
   23 |     vis[2000002] = 1;
      |     ~~~~~~~~~~~^
teleporters.cpp:8:6: note: while referencing 'vis'
    8 | bool vis[2000002];
      |      ^~~

• 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