Submission #724553

#	Time	Username	Problem	Language	Result	Execution time	Memory
724553		khanhdz06	Teleporters (IOI08_teleporters)	C++17	100 / 100	358 ms	40800 KiB

teleporters

#include <iostream>
#include <vector>
#include <queue>
#define ep emplace
#define eb emplace_back
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const ll maxn=2e6+5;
const ll mod= 1e9+7 ;
const ll base=3e18 ;

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("cheetos.in","r"))
    {
        freopen("cheetos.in","r",stdin);
        freopen("cheetos.out","w",stdout);
    }
    for (ll i=0;i<maxn;i++)
    {
        tel[i]=i+1;
    }
    cin>> n>> m;
    for (ll i=1;i<=n;i++)
    {
        ll l, r;
        cin>> l>> r;
        tel[l-1]=r;
        tel[r-1]=l;
    }
    ll len=-1;
    vis[maxn]=1;
    for (ll i=0;i<maxn;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.ep(ret);
        }
    }
    while (!pq.empty()&&m)
    {
        len+=pq.top()+2;
        pq.pop();
        m--;
    }
    len+=(m+1)/2;
    len+=(m/2)*3;
    cout <<len;

}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("cheetos.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teleporters.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen("cheetos.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
teleporters.cpp:42:13: warning: array subscript 2000005 is above array bounds of 'bool [2000005]' [-Warray-bounds]
   42 |     vis[maxn]=1;
      |     ~~~~~~~~^
teleporters.cpp:16:6: note: while referencing 'vis'
   16 | bool vis[maxn];
      |      ^~~

• 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