oj.uz

Submission #569209

# Submission time Handle Problem Language Result Execution time Memory
569209 2022-05-27T04:04:48 Z pavement Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 307 ms 21356 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back

ll ans;
int n, vsz, diff[400005], link[400005], sz[400005];
vector<int> vec;
vector<tuple<int, int, int> > ed;

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

int disc(int x) {
	return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	s.pb(1e9);
	t.pb(1);
	n = s.size();
	for (int i = 0; i < n; i++)
		vec.pb(s[i]), vec.pb(t[i]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for (int i = 0; i < n; i++) {
		diff[disc(s[i])]++;
		diff[disc(t[i])]--;
	}
	vsz = vec.size();
	for (int i = 0; i < vsz; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 0; i < n; i++)
		unite(disc(s[i]), disc(t[i]));
	for (int i = 0, bal = 0; i < vsz; i++) {
		bal += diff[i];
		if (i == vsz - 1) assert(bal == 0);
		if (bal > 0) ans += (ll)bal * (ll)(vec[i + 1] - vec[i]);
		if (bal) unite(i, i + 1);
	}
	for (int i = 0; i < vsz - 1; i++) ed.emplace_back(vec[i + 1] - vec[i], i, i + 1);
	sort(ed.begin(), ed.end());
	for (auto [w, u, v] : ed)
		if (find(u) != find(v)) unite(u, v), ans += (ll)w;
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 0 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 0 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 0 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 0 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 0 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 0 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 0 ms 212 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 17312 KB n = 199999
2 Correct 260 ms 21304 KB n = 199991
3 Correct 307 ms 21280 KB n = 199993
4 Correct 184 ms 17688 KB n = 152076
5 Correct 106 ms 10256 KB n = 93249
6 Correct 222 ms 19236 KB n = 199910
7 Correct 260 ms 20432 KB n = 199999
8 Correct 225 ms 19344 KB n = 199997
9 Correct 218 ms 19224 KB n = 171294
10 Correct 202 ms 17452 KB n = 140872
11 Correct 236 ms 19368 KB n = 199886
12 Correct 232 ms 20512 KB n = 199996
13 Correct 226 ms 19620 KB n = 200000
14 Correct 273 ms 20368 KB n = 199998
15 Correct 232 ms 20256 KB n = 200000
16 Correct 238 ms 20700 KB n = 199998
17 Correct 237 ms 21256 KB n = 200000
18 Correct 306 ms 20504 KB n = 190000
19 Correct 216 ms 19868 KB n = 177777
20 Correct 116 ms 10900 KB n = 100000
21 Correct 294 ms 21260 KB n = 200000
22 Correct 241 ms 21284 KB n = 200000
23 Correct 264 ms 21332 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 0 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 0 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 0 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 0 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 0 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 0 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 0 ms 212 KB n = 16
49 Correct 282 ms 17312 KB n = 199999
50 Correct 260 ms 21304 KB n = 199991
51 Correct 307 ms 21280 KB n = 199993
52 Correct 184 ms 17688 KB n = 152076
53 Correct 106 ms 10256 KB n = 93249
54 Correct 222 ms 19236 KB n = 199910
55 Correct 260 ms 20432 KB n = 199999
56 Correct 225 ms 19344 KB n = 199997
57 Correct 218 ms 19224 KB n = 171294
58 Correct 202 ms 17452 KB n = 140872
59 Correct 236 ms 19368 KB n = 199886
60 Correct 232 ms 20512 KB n = 199996
61 Correct 226 ms 19620 KB n = 200000
62 Correct 273 ms 20368 KB n = 199998
63 Correct 232 ms 20256 KB n = 200000
64 Correct 238 ms 20700 KB n = 199998
65 Correct 237 ms 21256 KB n = 200000
66 Correct 306 ms 20504 KB n = 190000
67 Correct 216 ms 19868 KB n = 177777
68 Correct 116 ms 10900 KB n = 100000
69 Correct 294 ms 21260 KB n = 200000
70 Correct 241 ms 21284 KB n = 200000
71 Correct 264 ms 21332 KB n = 200000
72 Correct 307 ms 21156 KB n = 200000
73 Correct 292 ms 21252 KB n = 200000
74 Correct 254 ms 21200 KB n = 200000
75 Correct 280 ms 21356 KB n = 200000
76 Correct 250 ms 21276 KB n = 200000
77 Correct 194 ms 15820 KB n = 200000
78 Correct 193 ms 15852 KB n = 200000
79 Correct 262 ms 20044 KB n = 184307
80 Correct 89 ms 9328 KB n = 76040
81 Correct 233 ms 19356 KB n = 199981
82 Correct 304 ms 20540 KB n = 199994
83 Correct 227 ms 19636 KB n = 199996
84 Correct 231 ms 20376 KB n = 199998
85 Correct 246 ms 20248 KB n = 200000
86 Correct 263 ms 20724 KB n = 199998
87 Correct 282 ms 21204 KB n = 200000
88 Correct 258 ms 21200 KB n = 200000
89 Correct 272 ms 21316 KB n = 200000
90 Correct 268 ms 21256 KB n = 200000
91 Correct 276 ms 21196 KB n = 200000
92 Correct 266 ms 21216 KB n = 200000