oj.uz

답안 #872814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872814 2023-11-13T20:48:05 Z islingr Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 154 ms 20364 KB 
#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for (auto i{a}; i < (b); ++i)
#define per(i, a, b) for (auto i{b}; i-- > (a); )
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }

using ll = long long;


#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    std::vector<int> parent_or_size;
};

}  // namespace atcoder


ll plan_roller_coaster(vector<int> s, vector<int> t) {
	constexpr int inf = int(1e9) + 30;
	s.push_back(inf);
	t.push_back(1);

	auto cmp = t;
	cmp.insert(cmp.end(), all(s));
	sort(all(cmp));
	cmp.erase(unique(all(cmp)), end(cmp));

	auto hsh = [&](int x) -> int {
		return lower_bound(all(cmp), x) - begin(cmp);
	};
	const int m = sz(cmp);
	const int n = sz(s);

	atcoder::dsu g(m);
	vector<ll> bal(m);
	rep(i, 0, n) {
		const auto L = hsh(s[i]);
		const auto R = hsh(t[i]);
		++bal[L];
		--bal[R];

		g.merge(L, R);
	}
	rep(i, 0, m - 1) bal[i + 1] += bal[i];
	assert(bal.back() == 0);

	vector<pair<ll, int>> mst;

	ll res = 0;
	rep(i, 0, m - 1) {
		const auto len = cmp[i + 1] - cmp[i];
		res += max(0ll, bal[i] * len);

		if (bal[i] == 0) mst.emplace_back(len, i);
		else g.merge(i, i + 1);
	}

	sort(all(mst));
	for (auto [len, i] : mst)
		if (not g.same(i, i + 1)) {
			g.merge(i, i + 1);
			res += len;
		}
	return res;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 512 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 600 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 0 ms 348 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 0 ms 348 KB n = 8
11 Correct 0 ms 436 KB n = 8
12 Correct 0 ms 600 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 432 KB n = 8
15 Correct 0 ms 344 KB n = 8
16 Correct 0 ms 432 KB n = 8
17 Correct 0 ms 440 KB n = 8
18 Correct 0 ms 436 KB n = 8
19 Correct 0 ms 348 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 348 KB n = 8
22 Correct 0 ms 348 KB n = 8
23 Correct 0 ms 348 KB n = 8
24 Correct 0 ms 440 KB n = 8
25 Correct 0 ms 348 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 512 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 600 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 0 ms 348 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 0 ms 348 KB n = 8
11 Correct 0 ms 436 KB n = 8
12 Correct 0 ms 600 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 432 KB n = 8
15 Correct 0 ms 344 KB n = 8
16 Correct 0 ms 432 KB n = 8
17 Correct 0 ms 440 KB n = 8
18 Correct 0 ms 436 KB n = 8
19 Correct 0 ms 348 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 348 KB n = 8
22 Correct 0 ms 348 KB n = 8
23 Correct 0 ms 348 KB n = 8
24 Correct 0 ms 440 KB n = 8
25 Correct 0 ms 348 KB n = 8
26 Correct 1 ms 348 KB n = 8
27 Correct 0 ms 432 KB n = 8
28 Correct 0 ms 344 KB n = 8
29 Correct 0 ms 348 KB n = 16
30 Correct 0 ms 348 KB n = 16
31 Correct 0 ms 440 KB n = 16
32 Correct 0 ms 348 KB n = 16
33 Correct 0 ms 348 KB n = 16
34 Correct 0 ms 348 KB n = 16
35 Correct 0 ms 348 KB n = 16
36 Correct 0 ms 348 KB n = 15
37 Correct 0 ms 348 KB n = 8
38 Correct 0 ms 440 KB n = 16
39 Correct 0 ms 348 KB n = 16
40 Correct 0 ms 348 KB n = 9
41 Correct 0 ms 348 KB n = 16
42 Correct 0 ms 348 KB n = 16
43 Correct 0 ms 376 KB n = 16
44 Correct 0 ms 348 KB n = 9
45 Correct 0 ms 348 KB n = 15
46 Correct 0 ms 348 KB n = 16
47 Correct 0 ms 428 KB n = 16
48 Correct 0 ms 348 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 10524 KB n = 199999
2 Correct 128 ms 14480 KB n = 199991
3 Correct 130 ms 14384 KB n = 199993
4 Correct 88 ms 10552 KB n = 152076
5 Correct 56 ms 7204 KB n = 93249
6 Correct 111 ms 12340 KB n = 199910
7 Correct 120 ms 13616 KB n = 199999
8 Correct 111 ms 12548 KB n = 199997
9 Correct 104 ms 12076 KB n = 171294
10 Correct 81 ms 10248 KB n = 140872
11 Correct 114 ms 12516 KB n = 199886
12 Correct 115 ms 13736 KB n = 199996
13 Correct 120 ms 12808 KB n = 200000
14 Correct 125 ms 18992 KB n = 199998
15 Correct 128 ms 19180 KB n = 200000
16 Correct 136 ms 18220 KB n = 199998
17 Correct 121 ms 14384 KB n = 200000
18 Correct 114 ms 13780 KB n = 190000
19 Correct 110 ms 12772 KB n = 177777
20 Correct 55 ms 7452 KB n = 100000
21 Correct 121 ms 14512 KB n = 200000
22 Correct 143 ms 20364 KB n = 200000
23 Correct 154 ms 18988 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 512 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 600 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 0 ms 348 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 0 ms 348 KB n = 8
11 Correct 0 ms 436 KB n = 8
12 Correct 0 ms 600 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 432 KB n = 8
15 Correct 0 ms 344 KB n = 8
16 Correct 0 ms 432 KB n = 8
17 Correct 0 ms 440 KB n = 8
18 Correct 0 ms 436 KB n = 8
19 Correct 0 ms 348 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 348 KB n = 8
22 Correct 0 ms 348 KB n = 8
23 Correct 0 ms 348 KB n = 8
24 Correct 0 ms 440 KB n = 8
25 Correct 0 ms 348 KB n = 8
26 Correct 1 ms 348 KB n = 8
27 Correct 0 ms 432 KB n = 8
28 Correct 0 ms 344 KB n = 8
29 Correct 0 ms 348 KB n = 16
30 Correct 0 ms 348 KB n = 16
31 Correct 0 ms 440 KB n = 16
32 Correct 0 ms 348 KB n = 16
33 Correct 0 ms 348 KB n = 16
34 Correct 0 ms 348 KB n = 16
35 Correct 0 ms 348 KB n = 16
36 Correct 0 ms 348 KB n = 15
37 Correct 0 ms 348 KB n = 8
38 Correct 0 ms 440 KB n = 16
39 Correct 0 ms 348 KB n = 16
40 Correct 0 ms 348 KB n = 9
41 Correct 0 ms 348 KB n = 16
42 Correct 0 ms 348 KB n = 16
43 Correct 0 ms 376 KB n = 16
44 Correct 0 ms 348 KB n = 9
45 Correct 0 ms 348 KB n = 15
46 Correct 0 ms 348 KB n = 16
47 Correct 0 ms 428 KB n = 16
48 Correct 0 ms 348 KB n = 16
49 Correct 118 ms 10524 KB n = 199999
50 Correct 128 ms 14480 KB n = 199991
51 Correct 130 ms 14384 KB n = 199993
52 Correct 88 ms 10552 KB n = 152076
53 Correct 56 ms 7204 KB n = 93249
54 Correct 111 ms 12340 KB n = 199910
55 Correct 120 ms 13616 KB n = 199999
56 Correct 111 ms 12548 KB n = 199997
57 Correct 104 ms 12076 KB n = 171294
58 Correct 81 ms 10248 KB n = 140872
59 Correct 114 ms 12516 KB n = 199886
60 Correct 115 ms 13736 KB n = 199996
61 Correct 120 ms 12808 KB n = 200000
62 Correct 125 ms 18992 KB n = 199998
63 Correct 128 ms 19180 KB n = 200000
64 Correct 136 ms 18220 KB n = 199998
65 Correct 121 ms 14384 KB n = 200000
66 Correct 114 ms 13780 KB n = 190000
67 Correct 110 ms 12772 KB n = 177777
68 Correct 55 ms 7452 KB n = 100000
69 Correct 121 ms 14512 KB n = 200000
70 Correct 143 ms 20364 KB n = 200000
71 Correct 154 ms 18988 KB n = 200000
72 Correct 120 ms 14492 KB n = 200000
73 Correct 130 ms 14364 KB n = 200000
74 Correct 118 ms 14384 KB n = 200000
75 Correct 119 ms 14384 KB n = 200000
76 Correct 123 ms 14548 KB n = 200000
77 Correct 107 ms 11316 KB n = 200000
78 Correct 129 ms 16416 KB n = 200000
79 Correct 112 ms 13084 KB n = 184307
80 Correct 43 ms 5624 KB n = 76040
81 Correct 113 ms 12336 KB n = 199981
82 Correct 118 ms 13616 KB n = 199994
83 Correct 118 ms 12836 KB n = 199996
84 Correct 129 ms 18340 KB n = 199998
85 Correct 128 ms 17896 KB n = 200000
86 Correct 131 ms 18588 KB n = 199998
87 Correct 129 ms 14396 KB n = 200000
88 Correct 125 ms 14380 KB n = 200000
89 Correct 122 ms 14388 KB n = 200000
90 Correct 118 ms 14744 KB n = 200000
91 Correct 144 ms 18988 KB n = 200000
92 Correct 146 ms 19368 KB n = 200000