oj.uz

Submission #54080

# Submission time Handle Problem Language Result Execution time Memory
54080 2018-07-02T09:48:44 Z imeimi2000 Teleporters (IOI08_teleporters) C++17
100 / 100
 577 ms 34160 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;
int s[1000000];
int e[1000000];
pii comp[2000000];
int to[2000000];
bool visited[2000001];
int arr[2000000];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> s[i] >> e[i];
        comp[i << 1 | 0] = pii(s[i], i << 1 | 0);
        comp[i << 1 | 1] = pii(e[i], i << 1 | 1);
    }
    sort(comp, comp + (n << 1));
    for (int i = 0; i < (n << 1); ++i) {
        if (comp[i].second & 1) e[comp[i].second >> 1] = i + 1;
        else s[comp[i].second >> 1] = i + 1;
    }
    for (int i = 0; i < n; ++i) {
        to[s[i]] = e[i];
        to[e[i]] = s[i];
    }
    visited[n << 1] = 1;
    int sz = -1;
    for (int i = 0; i < (n << 1); ++i) {
        if (visited[i]) continue;
        int x = to[i + 1];
        visited[i] = 1;
        int s = 1;
        while (!visited[x]) {
            visited[x] = 1;
            x = to[x + 1];
            ++s;
        }
        if (sz != -1) ++arr[s];
        else sz = s;
    }
    for (int i = 2 * n - 1; i > 0 && m > 0; --i) {
        while (arr[i] > 0 && m > 0) {
            sz += i + 2;
            --arr[i];
            --m;
        }
    }
    printf("%d\n", sz + ((m >> 1) << 2) + (m & 1));
    
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 6 ms 1008 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1008 KB Output is correct
2 Correct 7 ms 1032 KB Output is correct
3 Correct 18 ms 1644 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1644 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1644 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4760 KB Output is correct
2 Correct 155 ms 10604 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 10604 KB Output is correct
2 Correct 245 ms 15464 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 21404 KB Output is correct
2 Correct 388 ms 25708 KB Output is correct
3 Correct 423 ms 27904 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 29856 KB Output is correct
2 Correct 540 ms 32652 KB Output is correct
3 Correct 523 ms 33608 KB Output is correct
4 Correct 534 ms 33868 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 33868 KB Output is correct
2 Correct 577 ms 34028 KB Output is correct
3 Correct 419 ms 34160 KB Output is correct
4 Correct 496 ms 34160 KB Output is correct