oj.uz

Submission #602875

# Submission time Handle Problem Language Result Execution time Memory
602875 2022-07-23T12:07:29 Z 8e7 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 117 ms 19792 KB 
#include "railroad.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;
struct DSU{
	int par[maxn];
	void init(int n){
		for (int i = 0;i <= n;i++) par[i] = i;
	}
	int find(int a){
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b){
		a = find(a), b = find(b);
		if (a == b) return 0;
		par[a] = b;
		return 1;
	}
} dsu;

struct obj{
	int pos, val, id;
	obj(){pos = val = id = 0;}
	obj(int a, int b, int c){pos = a, val = b, id = c;}
};
int vis[maxn];
long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    int n = (int) S.size();
	vector<obj> a, ed;
	for (int i = 0;i < n;i++) {
		a.push_back(obj(S[i], 1, i));
		a.push_back(obj(T[i], -1, i));
	}
	a.push_back(obj(1<<30, 1, n));
	a.push_back(obj(1, -1, n));
	sort(a.begin(),a.end(), [&] (obj x, obj y){return x.pos < y.pos;});

	int siz = 2*n + 2;
	dsu.init(siz);
	
	ll cur = 0, x = 1;
	ll ans = 0;
	int ind = 0;
	for (auto [pos, val, id]:a) {
		if (cur != 0) {
			ans += max(cur, 0LL) * (pos - x);	
			dsu.Union(ind, ind-1);	
		} else if (ind){
			ed.push_back(obj(ind, ind-1, pos - x));
		}
		x = pos;
		cur += val;
		if (vis[id]) {
			dsu.Union(ind, vis[id]-1);
		} else {
			vis[id] = ind+1;
		}
		ind++;
	}
	debug(ans);
	sort(ed.begin(), ed.end(), [&] (obj x, obj y){return x.id < y.id;});
	for (auto [u, v, w]:ed) {
		if (dsu.Union(u, v)) ans += w;
	}	
    return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
railroad.cpp:77:2: note: in expansion of macro 'debug'
   77 |  debug(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 308 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 320 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 0 ms 312 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 464 KB n = 8
15 Correct 1 ms 308 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 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 300 KB n = 8
25 Correct 0 ms 308 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 308 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 320 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 0 ms 312 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 464 KB n = 8
15 Correct 1 ms 308 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 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 300 KB n = 8
25 Correct 0 ms 308 KB n = 8
26 Correct 1 ms 308 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 308 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 216 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 308 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 304 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 0 ms 212 KB n = 16
48 Correct 1 ms 308 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 14376 KB n = 199999
2 Correct 93 ms 14448 KB n = 199991
3 Correct 85 ms 14380 KB n = 199993
4 Correct 68 ms 11580 KB n = 152076
5 Correct 40 ms 6916 KB n = 93249
6 Correct 82 ms 13220 KB n = 199910
7 Correct 85 ms 13712 KB n = 199999
8 Correct 100 ms 13352 KB n = 199997
9 Correct 100 ms 12372 KB n = 171294
10 Correct 64 ms 11452 KB n = 140872
11 Correct 83 ms 13332 KB n = 199886
12 Correct 86 ms 14252 KB n = 199996
13 Correct 89 ms 13916 KB n = 200000
14 Correct 98 ms 18332 KB n = 199998
15 Correct 115 ms 18340 KB n = 200000
16 Correct 105 ms 18824 KB n = 199998
17 Correct 82 ms 14512 KB n = 200000
18 Correct 86 ms 13720 KB n = 190000
19 Correct 84 ms 12808 KB n = 177777
20 Correct 45 ms 7356 KB n = 100000
21 Correct 102 ms 14432 KB n = 200000
22 Correct 115 ms 19740 KB n = 200000
23 Correct 112 ms 19760 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 308 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 320 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 0 ms 312 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 464 KB n = 8
15 Correct 1 ms 308 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 304 KB n = 7
21 Correct 1 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 300 KB n = 8
25 Correct 0 ms 308 KB n = 8
26 Correct 1 ms 308 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 308 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 216 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 308 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 212 KB n = 9
45 Correct 1 ms 304 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 0 ms 212 KB n = 16
48 Correct 1 ms 308 KB n = 16
49 Correct 88 ms 14376 KB n = 199999
50 Correct 93 ms 14448 KB n = 199991
51 Correct 85 ms 14380 KB n = 199993
52 Correct 68 ms 11580 KB n = 152076
53 Correct 40 ms 6916 KB n = 93249
54 Correct 82 ms 13220 KB n = 199910
55 Correct 85 ms 13712 KB n = 199999
56 Correct 100 ms 13352 KB n = 199997
57 Correct 100 ms 12372 KB n = 171294
58 Correct 64 ms 11452 KB n = 140872
59 Correct 83 ms 13332 KB n = 199886
60 Correct 86 ms 14252 KB n = 199996
61 Correct 89 ms 13916 KB n = 200000
62 Correct 98 ms 18332 KB n = 199998
63 Correct 115 ms 18340 KB n = 200000
64 Correct 105 ms 18824 KB n = 199998
65 Correct 82 ms 14512 KB n = 200000
66 Correct 86 ms 13720 KB n = 190000
67 Correct 84 ms 12808 KB n = 177777
68 Correct 45 ms 7356 KB n = 100000
69 Correct 102 ms 14432 KB n = 200000
70 Correct 115 ms 19740 KB n = 200000
71 Correct 112 ms 19760 KB n = 200000
72 Correct 94 ms 14496 KB n = 200000
73 Correct 95 ms 14440 KB n = 200000
74 Correct 109 ms 14444 KB n = 200000
75 Correct 84 ms 14376 KB n = 200000
76 Correct 85 ms 14376 KB n = 200000
77 Correct 91 ms 17076 KB n = 200000
78 Correct 105 ms 19788 KB n = 200000
79 Correct 84 ms 13088 KB n = 184307
80 Correct 34 ms 6144 KB n = 76040
81 Correct 88 ms 13332 KB n = 199981
82 Correct 92 ms 14244 KB n = 199994
83 Correct 87 ms 13980 KB n = 199996
84 Correct 99 ms 18340 KB n = 199998
85 Correct 109 ms 18336 KB n = 200000
86 Correct 110 ms 18828 KB n = 199998
87 Correct 83 ms 14364 KB n = 200000
88 Correct 86 ms 14448 KB n = 200000
89 Correct 90 ms 14440 KB n = 200000
90 Correct 94 ms 14436 KB n = 200000
91 Correct 117 ms 19748 KB n = 200000
92 Correct 110 ms 19792 KB n = 200000