oj.uz

Submission #121188

# Submission time Handle Problem Language Result Execution time Memory
121188 2019-06-26T07:47:46 Z WhipppedCream Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 460 ms 44480 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n;

const int maxN = 4e5+5;

int sw[maxN];
vector<int> adj[maxN];
int s[maxN], t[maxN];

struct dsu
{
	int par[maxN];
	int cc;
	dsu(int n = 0)
	{
		for(int i = 0; i< n; i++) par[i] = i;
		cc = n;
	}
	int findset(int x)
	{
		if(x == par[x]) return x;
		return par[x] = findset(par[x]);
	}
	void unionset(int x, int y)
	{
		int a = findset(x), b = findset(y);
		if(a == b) return;
		cc--;
		par[a] = b;
	}
};

dsu foo;

ll plan_roller_coaster(vector<int> S, vector<int> T)
{
	n = S.size();
	for(int i = 0; i< n; i++)
	{
		s[i] = S[i];
		t[i] = T[i];
	}
	vector<int> all;
	for(int i = 0; i< n; i++)
	{
		all.pb(s[i]); all.pb(t[i]);
	}
	all.pb(1); all.pb(1e9);
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end())-all.begin());

	foo = dsu( (int) all.size());
	sw[0]++;
	sw[all.size()-1]--;
	adj[all.size()-1].pb(0);
	foo.unionset(all.size()-1, 0);
	for(int i = 0; i< n; i++)
	{
		int ss = lower_bound(all.begin(), all.end(), s[i])-all.begin();
		int tt = lower_bound(all.begin(), all.end(), t[i])-all.begin();
		sw[ss]--;
		sw[tt]++;
		adj[ss].pb(tt);
		foo.unionset(ss, tt);
	}
	int run = 0;
	ll base = 0;
	for(int i = 0; i+1< (int) all.size(); i++)
	{
		run += sw[i];
		if(run> 0) 
		{
			adj[i].pb(i+1);
			foo.unionset(i, i+1);
		}
		if(run< 0)
		{
			adj[i+1].pb(i);
			base += 1LL*-run*(all[i+1]-all[i]);
			foo.unionset(i+1, i);
		}
	}
	vector< ii > edges;
	for(int i = 0; i+1< (int) all.size(); i++)
	{
		edges.pb({all[i+1]-all[i], i});
	}
	sort(edges.begin(), edges.end());
	for(ii kk : edges)
	{
		int w = kk.X, u = kk.Y;
		int x = foo.findset(u), y = foo.findset(u+1);
		if(x == y) continue;
		foo.unionset(x, y);
		base += w;
		if(foo.cc == 1) break;
	}
	return base;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 37504 KB n = 199999
2 Correct 460 ms 37608 KB n = 199991
3 Correct 354 ms 37488 KB n = 199993
4 Correct 266 ms 32360 KB n = 152076
5 Correct 165 ms 23916 KB n = 93249
6 Correct 331 ms 34796 KB n = 199910
7 Correct 335 ms 37736 KB n = 199999
8 Correct 304 ms 35332 KB n = 199997
9 Correct 304 ms 34384 KB n = 171294
10 Correct 251 ms 31080 KB n = 140872
11 Correct 333 ms 34984 KB n = 199886
12 Correct 335 ms 37968 KB n = 199996
13 Correct 310 ms 36044 KB n = 200000
14 Correct 324 ms 39404 KB n = 199998
15 Correct 301 ms 38472 KB n = 200000
16 Correct 322 ms 38852 KB n = 199998
17 Correct 318 ms 37608 KB n = 200000
18 Correct 338 ms 36748 KB n = 190000
19 Correct 288 ms 37916 KB n = 177777
20 Correct 167 ms 24604 KB n = 100000
21 Correct 369 ms 37572 KB n = 200000
22 Correct 323 ms 37492 KB n = 200000
23 Correct 340 ms 37544 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11264 KB n = 2
2 Correct 13 ms 11264 KB n = 2
3 Correct 12 ms 11264 KB n = 2
4 Correct 12 ms 11392 KB n = 2
5 Correct 11 ms 11264 KB n = 2
6 Correct 11 ms 11392 KB n = 2
7 Correct 11 ms 11264 KB n = 3
8 Correct 14 ms 11264 KB n = 3
9 Correct 12 ms 11236 KB n = 3
10 Correct 12 ms 11264 KB n = 8
11 Correct 12 ms 11264 KB n = 8
12 Correct 12 ms 11264 KB n = 8
13 Correct 12 ms 11264 KB n = 8
14 Correct 14 ms 11392 KB n = 8
15 Correct 12 ms 11264 KB n = 8
16 Correct 12 ms 11392 KB n = 8
17 Correct 12 ms 11264 KB n = 8
18 Correct 12 ms 11264 KB n = 8
19 Correct 12 ms 11392 KB n = 3
20 Correct 13 ms 11288 KB n = 7
21 Correct 13 ms 11264 KB n = 8
22 Correct 11 ms 11264 KB n = 8
23 Correct 12 ms 11264 KB n = 8
24 Correct 12 ms 11264 KB n = 8
25 Correct 14 ms 11264 KB n = 8
26 Correct 12 ms 11264 KB n = 8
27 Correct 12 ms 11264 KB n = 8
28 Correct 12 ms 11264 KB n = 8
29 Correct 11 ms 11264 KB n = 16
30 Correct 12 ms 11392 KB n = 16
31 Correct 11 ms 11264 KB n = 16
32 Correct 14 ms 11392 KB n = 16
33 Correct 12 ms 11264 KB n = 16
34 Correct 12 ms 11264 KB n = 16
35 Correct 12 ms 11264 KB n = 16
36 Correct 11 ms 11264 KB n = 15
37 Correct 11 ms 11264 KB n = 8
38 Correct 11 ms 11264 KB n = 16
39 Correct 12 ms 11392 KB n = 16
40 Correct 11 ms 11392 KB n = 9
41 Correct 12 ms 11264 KB n = 16
42 Correct 14 ms 11264 KB n = 16
43 Correct 12 ms 11392 KB n = 16
44 Correct 12 ms 11264 KB n = 9
45 Correct 12 ms 11392 KB n = 15
46 Correct 13 ms 11264 KB n = 16
47 Correct 12 ms 11264 KB n = 16
48 Correct 12 ms 11392 KB n = 16
49 Correct 393 ms 37504 KB n = 199999
50 Correct 460 ms 37608 KB n = 199991
51 Correct 354 ms 37488 KB n = 199993
52 Correct 266 ms 32360 KB n = 152076
53 Correct 165 ms 23916 KB n = 93249
54 Correct 331 ms 34796 KB n = 199910
55 Correct 335 ms 37736 KB n = 199999
56 Correct 304 ms 35332 KB n = 199997
57 Correct 304 ms 34384 KB n = 171294
58 Correct 251 ms 31080 KB n = 140872
59 Correct 333 ms 34984 KB n = 199886
60 Correct 335 ms 37968 KB n = 199996
61 Correct 310 ms 36044 KB n = 200000
62 Correct 324 ms 39404 KB n = 199998
63 Correct 301 ms 38472 KB n = 200000
64 Correct 322 ms 38852 KB n = 199998
65 Correct 318 ms 37608 KB n = 200000
66 Correct 338 ms 36748 KB n = 190000
67 Correct 288 ms 37916 KB n = 177777
68 Correct 167 ms 24604 KB n = 100000
69 Correct 369 ms 37572 KB n = 200000
70 Correct 323 ms 37492 KB n = 200000
71 Correct 340 ms 37544 KB n = 200000
72 Correct 376 ms 37652 KB n = 200000
73 Correct 379 ms 37564 KB n = 200000
74 Correct 369 ms 37604 KB n = 200000
75 Correct 324 ms 41360 KB n = 200000
76 Correct 332 ms 41308 KB n = 200000
77 Correct 295 ms 35432 KB n = 200000
78 Correct 238 ms 32336 KB n = 200000
79 Correct 350 ms 39072 KB n = 184307
80 Correct 128 ms 23312 KB n = 76040
81 Correct 301 ms 37740 KB n = 199981
82 Correct 356 ms 41156 KB n = 199994
83 Correct 321 ms 38732 KB n = 199996
84 Correct 311 ms 42320 KB n = 199998
85 Correct 326 ms 41420 KB n = 200000
86 Correct 364 ms 42136 KB n = 199998
87 Correct 333 ms 41344 KB n = 200000
88 Correct 367 ms 41592 KB n = 200000
89 Correct 338 ms 44480 KB n = 200000
90 Correct 370 ms 41392 KB n = 200000
91 Correct 317 ms 41288 KB n = 200000
92 Correct 334 ms 41332 KB n = 200000