oj.uz

Submission #724826

# Submission time Handle Problem Language Result Execution time Memory
724826 2023-04-16T03:57:22 Z khanhdz06 Teleporters (IOI08_teleporters) C++17
100 / 100
 383 ms 33844 KB 
#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

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

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17920 KB Output is correct
2 Correct 16 ms 18044 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18004 KB Output is correct
2 Correct 17 ms 18180 KB Output is correct
3 Correct 18 ms 18248 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20180 KB Output is correct
2 Correct 113 ms 23276 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 22092 KB Output is correct
2 Correct 184 ms 25576 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 29844 KB Output is correct
2 Correct 249 ms 29764 KB Output is correct
3 Correct 274 ms 33844 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 29720 KB Output is correct
2 Correct 331 ms 29512 KB Output is correct
3 Correct 285 ms 25188 KB Output is correct
4 Correct 266 ms 25292 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 33568 KB Output is correct
2 Correct 353 ms 33704 KB Output is correct
3 Correct 255 ms 33336 KB Output is correct
4 Correct 313 ms 33804 KB Output is correct