oj.uz

Submission #612964

# Submission time Handle Problem Language Result Execution time Memory
612964 2022-07-30T02:36:57 Z Temmie Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 941 ms 37564 KB 
#include <bits/stdc++.h>

struct Dsu {
	
	std::unordered_map <int, int> p;
	
	inline int find(int v) {
		return p.find(v) == p.end() || v == p[v] ? (p[v] = v) : (p[v] = find(p[v]));
	}
	
	inline bool unite(int u, int v) {
		if ((u = find(u)) == (v = find(v))) {
			return false;
		}
		p[u] = v;
		return true;
	}
	
};

std::vector <std::pair <int, int>> edv;
std::vector <int> edw;
std::vector <int> edi;

int MST(Dsu& dsu) {
	long long res = 0;
	for (int x : edi) {
		res += edw[x] * dsu.unite(edv[x].first, edv[x].second);
	}
	return res;
}

long long plan_roller_coaster(std::vector <int> s, std::vector <int> t) {
	int n = s.size();
	Dsu dsu;
	std::vector <std::pair <long long, long long>> ts(n << 1);
	for (int i = 0; i < n; i++) {
		dsu.unite(s[i], t[i]);
		ts[i * 2 + 0] = { s[i], 1 };
		ts[i * 2 + 1] = { t[i], -1 };
	}
	std::sort(ts.begin(), ts.end());
	long long ans = 0, is = -1;
	for (int i = 0; i < (n << 1) - 1; i++) {
		ans += std::max(0LL, (is += ts[i].second) * (ts[i + 1].first - ts[i].first));
		if (is) {
			dsu.unite(ts[i].first, ts[i + 1].first);
		} else {
			edw.push_back(ts[i + 1].first - ts[i].first);
			edv.emplace_back(ts[i].first, ts[i + 1].first);
		}
	}
	edi.resize(edw.size());
	std::iota(edi.begin(), edi.end(), 0);
	std::sort(edi.begin(), edi.end(), [&] (int u, int v) -> bool { return edw[u] < edw[v]; });
	return ans + MST(dsu);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 228 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 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 1 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 228 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 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 1 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 1 ms 212 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 236 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 28904 KB n = 199999
2 Correct 716 ms 28916 KB n = 199991
3 Correct 628 ms 32776 KB n = 199993
4 Correct 470 ms 22384 KB n = 152076
5 Correct 210 ms 16000 KB n = 93249
6 Correct 376 ms 25312 KB n = 199910
7 Correct 389 ms 32100 KB n = 199999
8 Correct 354 ms 25540 KB n = 199997
9 Correct 506 ms 24968 KB n = 171294
10 Correct 452 ms 21148 KB n = 140872
11 Correct 344 ms 25700 KB n = 199886
12 Correct 543 ms 32236 KB n = 199996
13 Correct 410 ms 26940 KB n = 200000
14 Correct 689 ms 37564 KB n = 199998
15 Correct 764 ms 35132 KB n = 200000
16 Correct 734 ms 36124 KB n = 199998
17 Correct 563 ms 36800 KB n = 200000
18 Correct 486 ms 32204 KB n = 190000
19 Correct 599 ms 33324 KB n = 177777
20 Correct 238 ms 16436 KB n = 100000
21 Correct 642 ms 32860 KB n = 200000
22 Correct 886 ms 36424 KB n = 200000
23 Correct 815 ms 36364 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 228 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 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 1 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 1 ms 212 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 236 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 212 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 658 ms 28904 KB n = 199999
50 Correct 716 ms 28916 KB n = 199991
51 Correct 628 ms 32776 KB n = 199993
52 Correct 470 ms 22384 KB n = 152076
53 Correct 210 ms 16000 KB n = 93249
54 Correct 376 ms 25312 KB n = 199910
55 Correct 389 ms 32100 KB n = 199999
56 Correct 354 ms 25540 KB n = 199997
57 Correct 506 ms 24968 KB n = 171294
58 Correct 452 ms 21148 KB n = 140872
59 Correct 344 ms 25700 KB n = 199886
60 Correct 543 ms 32236 KB n = 199996
61 Correct 410 ms 26940 KB n = 200000
62 Correct 689 ms 37564 KB n = 199998
63 Correct 764 ms 35132 KB n = 200000
64 Correct 734 ms 36124 KB n = 199998
65 Correct 563 ms 36800 KB n = 200000
66 Correct 486 ms 32204 KB n = 190000
67 Correct 599 ms 33324 KB n = 177777
68 Correct 238 ms 16436 KB n = 100000
69 Correct 642 ms 32860 KB n = 200000
70 Correct 886 ms 36424 KB n = 200000
71 Correct 815 ms 36364 KB n = 200000
72 Correct 744 ms 32864 KB n = 200000
73 Correct 740 ms 32768 KB n = 200000
74 Correct 834 ms 32872 KB n = 200000
75 Correct 596 ms 32880 KB n = 200000
76 Correct 534 ms 32868 KB n = 200000
77 Correct 255 ms 23080 KB n = 200000
78 Correct 531 ms 27224 KB n = 200000
79 Correct 728 ms 31648 KB n = 184307
80 Correct 259 ms 11492 KB n = 76040
81 Correct 382 ms 25652 KB n = 199981
82 Correct 435 ms 32376 KB n = 199994
83 Correct 342 ms 26972 KB n = 199996
84 Correct 657 ms 36252 KB n = 199998
85 Correct 655 ms 36388 KB n = 200000
86 Correct 787 ms 36656 KB n = 199998
87 Correct 688 ms 36908 KB n = 200000
88 Correct 600 ms 32884 KB n = 200000
89 Correct 746 ms 36872 KB n = 200000
90 Correct 639 ms 32884 KB n = 200000
91 Correct 862 ms 36412 KB n = 200000
92 Correct 941 ms 36420 KB n = 200000