oj.uz

Submission #332180

# Submission time Handle Problem Language Result Execution time Memory
332180 2020-12-01T15:25:13 Z nouvo25 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 232 ms 16472 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
using namespace std;
 
const int MAXN = 4e5 + 7;
 
int s[MAXN], t[MAXN], n, in[MAXN], out[MAXN], fa[MAXN];
vector<int> val;
 
void change(int &n)
{
	n = lower_bound(val.begin(), val.end(), n) - val.begin();
}
 
int root(int u)
{
	if (fa[u] < 0) return u;
	return fa[u] = root(fa[u]);
}
 
void join(int u, int v)
{
	u = root(u), v = root(v);
	if (u != v) fa[u] = v;
}
 
ll plan_roller_coaster(vector<int> s, vector<int> t)
//int main()
{
//	freopen("test.INP","r",stdin);
//	freopen("BAILAM.OUT","w",stdout);
//	io;
	n = (int)s.size();
//	cin >> n;
	for (int i = 0; i < n; ++i) 
	{
//		cin >> s[i] >> t[i];
		val.push_back(s[i]);
		val.push_back(t[i]);
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	
	int sz = (int)val.size();
	for (int i = 0; i < sz; ++i) fa[i] = -1;
	++out[sz - 1], ++in[0];
	join(0, sz - 1);
	for (int i = 0; i < n; ++i)
	{
		change(s[i]);
		change(t[i]);
		++out[s[i]], ++in[t[i]];
		join(s[i], t[i]);
	}
	
	vector< pair<int, pair<int,int> > > ed;
	ll res = 0;
	for (int i = sz - 1; i > 0; --i)
	{
		if (out[i] != in[i]) 
		{
			join(i, i - 1);
			if (out[i] > in[i]) out[i - 1] += (out[i] - in[i]);
			else in[i - 1] += (in[i] - out[i]), res += 1LL * (val[i] - val[i - 1]) * (in[i] - out[i]);
		}else ed.push_back({val[i] - val[i - 1], {i, i - 1}});
	}
//	cout << res << '\n';
	sort(ed.begin(), ed.end());
	for (auto it: ed)
	{
		int u = root(it.se.fi), v = root(it.se.se), cost = it.fi;
		if (u != v)
		{
			res += cost;
			fa[u] = v;
		}
	}
//	cout << res;
//	return 0;
	return res;
}

//int main()
//{
//	return 0;
//}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 9820 KB n = 199999
2 Correct 214 ms 9832 KB n = 199991
3 Correct 203 ms 9820 KB n = 199993
4 Correct 142 ms 7672 KB n = 152076
5 Correct 95 ms 4832 KB n = 93249
6 Correct 170 ms 9052 KB n = 199910
7 Correct 178 ms 10716 KB n = 199999
8 Correct 171 ms 9948 KB n = 199997
9 Correct 170 ms 8668 KB n = 171294
10 Correct 137 ms 7132 KB n = 140872
11 Correct 176 ms 9180 KB n = 199886
12 Correct 176 ms 11484 KB n = 199996
13 Correct 174 ms 10972 KB n = 200000
14 Correct 206 ms 16472 KB n = 199998
15 Correct 199 ms 15192 KB n = 200000
16 Correct 207 ms 15320 KB n = 199998
17 Correct 173 ms 15324 KB n = 200000
18 Correct 175 ms 10364 KB n = 190000
19 Correct 162 ms 13660 KB n = 177777
20 Correct 86 ms 5216 KB n = 100000
21 Correct 190 ms 9820 KB n = 200000
22 Correct 232 ms 14428 KB n = 200000
23 Correct 223 ms 14300 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 2
2 Correct 0 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 1 ms 364 KB n = 2
5 Correct 0 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 0 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 1 ms 364 KB n = 3
10 Correct 0 ms 364 KB n = 8
11 Correct 0 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 0 ms 364 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 0 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 0 ms 364 KB n = 3
20 Correct 1 ms 364 KB n = 7
21 Correct 0 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 512 KB n = 8
25 Correct 1 ms 364 KB n = 8
26 Correct 1 ms 364 KB n = 8
27 Correct 0 ms 364 KB n = 8
28 Correct 1 ms 364 KB n = 8
29 Correct 1 ms 364 KB n = 16
30 Correct 1 ms 364 KB n = 16
31 Correct 1 ms 364 KB n = 16
32 Correct 1 ms 364 KB n = 16
33 Correct 0 ms 364 KB n = 16
34 Correct 1 ms 364 KB n = 16
35 Correct 1 ms 364 KB n = 16
36 Correct 0 ms 364 KB n = 15
37 Correct 1 ms 364 KB n = 8
38 Correct 0 ms 364 KB n = 16
39 Correct 1 ms 364 KB n = 16
40 Correct 0 ms 364 KB n = 9
41 Correct 1 ms 364 KB n = 16
42 Correct 1 ms 364 KB n = 16
43 Correct 1 ms 364 KB n = 16
44 Correct 1 ms 364 KB n = 9
45 Correct 1 ms 364 KB n = 15
46 Correct 1 ms 364 KB n = 16
47 Correct 1 ms 364 KB n = 16
48 Correct 1 ms 364 KB n = 16
49 Correct 214 ms 9820 KB n = 199999
50 Correct 214 ms 9832 KB n = 199991
51 Correct 203 ms 9820 KB n = 199993
52 Correct 142 ms 7672 KB n = 152076
53 Correct 95 ms 4832 KB n = 93249
54 Correct 170 ms 9052 KB n = 199910
55 Correct 178 ms 10716 KB n = 199999
56 Correct 171 ms 9948 KB n = 199997
57 Correct 170 ms 8668 KB n = 171294
58 Correct 137 ms 7132 KB n = 140872
59 Correct 176 ms 9180 KB n = 199886
60 Correct 176 ms 11484 KB n = 199996
61 Correct 174 ms 10972 KB n = 200000
62 Correct 206 ms 16472 KB n = 199998
63 Correct 199 ms 15192 KB n = 200000
64 Correct 207 ms 15320 KB n = 199998
65 Correct 173 ms 15324 KB n = 200000
66 Correct 175 ms 10364 KB n = 190000
67 Correct 162 ms 13660 KB n = 177777
68 Correct 86 ms 5216 KB n = 100000
69 Correct 190 ms 9820 KB n = 200000
70 Correct 232 ms 14428 KB n = 200000
71 Correct 223 ms 14300 KB n = 200000
72 Correct 200 ms 9820 KB n = 200000
73 Correct 223 ms 9868 KB n = 200000
74 Correct 197 ms 9820 KB n = 200000
75 Correct 179 ms 9052 KB n = 200000
76 Correct 183 ms 9240 KB n = 200000
77 Correct 153 ms 13916 KB n = 200000
78 Correct 179 ms 12144 KB n = 200000
79 Correct 189 ms 9308 KB n = 184307
80 Correct 74 ms 4192 KB n = 76040
81 Correct 201 ms 9180 KB n = 199981
82 Correct 178 ms 11612 KB n = 199994
83 Correct 173 ms 10844 KB n = 199996
84 Correct 193 ms 16472 KB n = 199998
85 Correct 198 ms 15192 KB n = 200000
86 Correct 207 ms 15320 KB n = 199998
87 Correct 174 ms 15324 KB n = 200000
88 Correct 190 ms 10948 KB n = 200000
89 Correct 185 ms 15324 KB n = 200000
90 Correct 187 ms 9820 KB n = 200000
91 Correct 230 ms 14300 KB n = 200000
92 Correct 226 ms 14428 KB n = 200000