oj.uz

Submission #724553

# Submission time Handle Problem Language Result Execution time Memory
724553 2023-04-15T14:11:37 Z khanhdz06 Teleporters (IOI08_teleporters) C++17
100 / 100
 358 ms 40800 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17876 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17928 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17920 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17908 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17876 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17888 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17876 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17876 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17868 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17844 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17928 KB Output is correct
2 Correct 19 ms 18132 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17960 KB Output is correct
2 Correct 22 ms 18180 KB Output is correct
3 Correct 24 ms 18172 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18012 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18312 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20136 KB Output is correct
2 Correct 136 ms 23372 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 21972 KB Output is correct
2 Correct 175 ms 25556 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 31168 KB Output is correct
2 Correct 253 ms 33092 KB Output is correct
3 Correct 277 ms 38000 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 34944 KB Output is correct
2 Correct 317 ms 36068 KB Output is correct
3 Correct 261 ms 32196 KB Output is correct
4 Correct 265 ms 32472 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 40800 KB Output is correct
2 Correct 337 ms 40796 KB Output is correct
3 Correct 267 ms 40532 KB Output is correct
4 Correct 285 ms 40780 KB Output is correct