oj.uz

Submission #775390

# Submission time Handle Problem Language Result Execution time Memory
775390 2023-07-06T10:46:40 Z PoonYaPat Teleporters (IOI08_teleporters) C++14
100 / 100
 385 ms 56436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n,m,ed=2000005;
ll ans;
pii nxt[2000010];
bool vis[2000010];
priority_queue<ll> q;

ll dfs(int x) {
    if (vis[x]) return 0;
    vis[x]=true;
    return nxt[x].second+dfs(nxt[x].first);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<ed; ++i) nxt[i]=pii(i+1,0);
    for (int i=0; i<n; ++i) {
        int a,b; cin>>a>>b;
        nxt[a]=pii(b+1,1);
        nxt[b]=pii(a+1,1);
    }

    ans=dfs(0);
    for (int i=0; i<ed; ++i) if (!vis[i]) q.push(dfs(i));
    while (m--) {
        if (q.size()) ans+=(q.top()+2), q.pop();
        else q.push(1), ++ans;
    }
    cout<<ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33560 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33492 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33484 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33508 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33568 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33568 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33484 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33560 KB Output is correct
2 Correct 26 ms 33756 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33620 KB Output is correct
2 Correct 25 ms 33772 KB Output is correct
3 Correct 29 ms 33836 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33736 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33868 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35792 KB Output is correct
2 Correct 121 ms 39032 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 37652 KB Output is correct
2 Correct 184 ms 41212 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 46844 KB Output is correct
2 Correct 239 ms 48624 KB Output is correct
3 Correct 263 ms 53608 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 50524 KB Output is correct
2 Correct 313 ms 51704 KB Output is correct
3 Correct 271 ms 47864 KB Output is correct
4 Correct 280 ms 47988 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 56420 KB Output is correct
2 Correct 319 ms 56428 KB Output is correct
3 Correct 216 ms 56040 KB Output is correct
4 Correct 250 ms 56436 KB Output is correct