oj.uz

Submission #302457

# Submission time Handle Problem Language Result Execution time Memory
302457 2020-09-18T17:21:24 Z Autoratch Teleporters (IOI08_teleporters) C++14
100 / 100
 466 ms 44408 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n,m,adj[N],dp[N],st[N],id,cm,sz[N];
bool visited[N];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for(int i = 0,a,b;i < n;i++) cin >> a >> b,adj[a] = b,adj[b] = a,dp[a]++,dp[b]++;
    for(int i = 1;i < N;i++)
    {
        dp[i]+=dp[i-1];
        if(dp[i]!=dp[i-1]) st[id++] = i;
    }   
    for(int i = 0;i < n*2;i++) if(!visited[i])
    {
        cm++;
        visited[i] = true;
        int u = i;
        while(true)
        {
            sz[cm]++;
            int v = dp[adj[st[u]]];
            if(visited[v] or v==n*2) break;
            visited[v] = true;
            u = v;
        }
    }
    int ans = sz[1];
    for(int i = 2;i <= cm;i++) dp[i-2] = sz[i];
    sort(dp,dp+cm-1);
    reverse(dp,dp+cm-1);
    for(int i = 0;i < cm-1 and m;i++,m--) ans+=dp[i]+2;
    if(m) ans+=2*(m-(m&1))+(m&1);
    cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8192 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8320 KB Output is correct
2 Correct 16 ms 8700 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8320 KB Output is correct
2 Correct 15 ms 8960 KB Output is correct
3 Correct 18 ms 9088 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13304 KB Output is correct
2 Correct 169 ms 22264 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 18424 KB Output is correct
2 Correct 250 ms 27468 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 33020 KB Output is correct
2 Correct 341 ms 36472 KB Output is correct
3 Correct 290 ms 37624 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 38776 KB Output is correct
2 Correct 466 ms 41080 KB Output is correct
3 Correct 343 ms 40312 KB Output is correct
4 Correct 349 ms 40568 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 43000 KB Output is correct
2 Correct 449 ms 43256 KB Output is correct
3 Correct 260 ms 44280 KB Output is correct
4 Correct 361 ms 44408 KB Output is correct