oj.uz

답안 #722580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722580 2023-04-12T11:46:06 Z ymm Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 433 ms 51268 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 400010;

vector<int> A[N];
int vis[N];

void dfs(int v, int c)
{
	vis[v] = c;
	for (int u : A[v])
		if (vis[u] == -1)
			dfs(u, c);
}

namespace dsu {
	int par[N];
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
	s.push_back(1e9+10);
	t.push_back(1);
	int n = s.size();
	vector<int> cmp;
	Loop (i,0,n) {
		cmp.push_back(s[i]);
		cmp.push_back(t[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	int m = cmp.size();
	vector<int> val(m);
	Loop (i,0,n) {
		int x = lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin();
		int y = lower_bound(cmp.begin(), cmp.end(), t[i]) - cmp.begin();
		A[x].push_back(y);
		A[y].push_back(x);
		val[x]--;
		val[y]++;
	}
	int cnt = 0;
	ll ans = 0;
	Loop (i,0,m-1) {
		cnt += val[i];
		if (cnt < 0)
			ans += (ll)(cmp[i+1] - cmp[i]) * -cnt;
		if (cnt) {
			A[i].push_back(i+1);
			A[i+1].push_back(i);
		}
	}
	int k = 0;
	memset(vis, -1, sizeof(vis));
	Loop (i,0,m) {
		if (vis[i] == -1)
			dfs(i, k++);
	}
	memset(dsu::par, -1, sizeof(dsu::par));
	vector<tuple<int,int,int>> E;
	Loop (i,0,m-1)
		E.push_back({cmp[i+1] - cmp[i], vis[i], vis[i+1]});
	sort(E.begin(), E.end());
	for (auto [w, v, u] : E) {
		if (dsu::unite(v, u)) {
			ans += w;
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB n = 2
2 Correct 7 ms 12828 KB n = 2
3 Correct 9 ms 12736 KB n = 2
4 Correct 6 ms 12756 KB n = 2
5 Correct 7 ms 12820 KB n = 2
6 Correct 6 ms 12732 KB n = 2
7 Correct 7 ms 12756 KB n = 3
8 Correct 6 ms 12756 KB n = 3
9 Correct 8 ms 12756 KB n = 3
10 Correct 7 ms 12756 KB n = 8
11 Correct 8 ms 12756 KB n = 8
12 Correct 7 ms 12776 KB n = 8
13 Correct 7 ms 12772 KB n = 8
14 Correct 7 ms 12768 KB n = 8
15 Correct 8 ms 12776 KB n = 8
16 Correct 8 ms 12768 KB n = 8
17 Correct 8 ms 12756 KB n = 8
18 Correct 7 ms 12772 KB n = 8
19 Correct 7 ms 12756 KB n = 3
20 Correct 7 ms 12756 KB n = 7
21 Correct 7 ms 12756 KB n = 8
22 Correct 6 ms 12756 KB n = 8
23 Correct 7 ms 12756 KB n = 8
24 Correct 7 ms 12756 KB n = 8
25 Correct 7 ms 12756 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB n = 2
2 Correct 7 ms 12828 KB n = 2
3 Correct 9 ms 12736 KB n = 2
4 Correct 6 ms 12756 KB n = 2
5 Correct 7 ms 12820 KB n = 2
6 Correct 6 ms 12732 KB n = 2
7 Correct 7 ms 12756 KB n = 3
8 Correct 6 ms 12756 KB n = 3
9 Correct 8 ms 12756 KB n = 3
10 Correct 7 ms 12756 KB n = 8
11 Correct 8 ms 12756 KB n = 8
12 Correct 7 ms 12776 KB n = 8
13 Correct 7 ms 12772 KB n = 8
14 Correct 7 ms 12768 KB n = 8
15 Correct 8 ms 12776 KB n = 8
16 Correct 8 ms 12768 KB n = 8
17 Correct 8 ms 12756 KB n = 8
18 Correct 7 ms 12772 KB n = 8
19 Correct 7 ms 12756 KB n = 3
20 Correct 7 ms 12756 KB n = 7
21 Correct 7 ms 12756 KB n = 8
22 Correct 6 ms 12756 KB n = 8
23 Correct 7 ms 12756 KB n = 8
24 Correct 7 ms 12756 KB n = 8
25 Correct 7 ms 12756 KB n = 8
26 Correct 7 ms 12756 KB n = 8
27 Correct 7 ms 12756 KB n = 8
28 Correct 7 ms 12756 KB n = 8
29 Correct 7 ms 12756 KB n = 16
30 Correct 7 ms 12756 KB n = 16
31 Correct 7 ms 12736 KB n = 16
32 Correct 7 ms 12772 KB n = 16
33 Correct 7 ms 12776 KB n = 16
34 Correct 7 ms 12772 KB n = 16
35 Correct 7 ms 12772 KB n = 16
36 Correct 7 ms 12756 KB n = 15
37 Correct 7 ms 12756 KB n = 8
38 Correct 8 ms 12756 KB n = 16
39 Correct 7 ms 12756 KB n = 16
40 Correct 6 ms 12756 KB n = 9
41 Correct 7 ms 12756 KB n = 16
42 Correct 7 ms 12776 KB n = 16
43 Correct 7 ms 12776 KB n = 16
44 Correct 8 ms 12780 KB n = 9
45 Correct 7 ms 12736 KB n = 15
46 Correct 7 ms 12780 KB n = 16
47 Correct 7 ms 12756 KB n = 16
48 Correct 7 ms 12832 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 45512 KB n = 199999
2 Correct 369 ms 45384 KB n = 199991
3 Correct 392 ms 45344 KB n = 199993
4 Correct 257 ms 39448 KB n = 152076
5 Correct 148 ms 28264 KB n = 93249
6 Correct 300 ms 40020 KB n = 199910
7 Correct 304 ms 42876 KB n = 199999
8 Correct 297 ms 40384 KB n = 199997
9 Correct 336 ms 40384 KB n = 171294
10 Correct 253 ms 38008 KB n = 140872
11 Correct 293 ms 42616 KB n = 199886
12 Correct 300 ms 46568 KB n = 199996
13 Correct 288 ms 43972 KB n = 200000
14 Correct 282 ms 48068 KB n = 199998
15 Correct 295 ms 47124 KB n = 200000
16 Correct 292 ms 48040 KB n = 199998
17 Correct 347 ms 51268 KB n = 200000
18 Correct 316 ms 49684 KB n = 190000
19 Correct 337 ms 47812 KB n = 177777
20 Correct 145 ms 30260 KB n = 100000
21 Correct 328 ms 48084 KB n = 200000
22 Correct 349 ms 43128 KB n = 200000
23 Correct 377 ms 51260 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB n = 2
2 Correct 7 ms 12828 KB n = 2
3 Correct 9 ms 12736 KB n = 2
4 Correct 6 ms 12756 KB n = 2
5 Correct 7 ms 12820 KB n = 2
6 Correct 6 ms 12732 KB n = 2
7 Correct 7 ms 12756 KB n = 3
8 Correct 6 ms 12756 KB n = 3
9 Correct 8 ms 12756 KB n = 3
10 Correct 7 ms 12756 KB n = 8
11 Correct 8 ms 12756 KB n = 8
12 Correct 7 ms 12776 KB n = 8
13 Correct 7 ms 12772 KB n = 8
14 Correct 7 ms 12768 KB n = 8
15 Correct 8 ms 12776 KB n = 8
16 Correct 8 ms 12768 KB n = 8
17 Correct 8 ms 12756 KB n = 8
18 Correct 7 ms 12772 KB n = 8
19 Correct 7 ms 12756 KB n = 3
20 Correct 7 ms 12756 KB n = 7
21 Correct 7 ms 12756 KB n = 8
22 Correct 6 ms 12756 KB n = 8
23 Correct 7 ms 12756 KB n = 8
24 Correct 7 ms 12756 KB n = 8
25 Correct 7 ms 12756 KB n = 8
26 Correct 7 ms 12756 KB n = 8
27 Correct 7 ms 12756 KB n = 8
28 Correct 7 ms 12756 KB n = 8
29 Correct 7 ms 12756 KB n = 16
30 Correct 7 ms 12756 KB n = 16
31 Correct 7 ms 12736 KB n = 16
32 Correct 7 ms 12772 KB n = 16
33 Correct 7 ms 12776 KB n = 16
34 Correct 7 ms 12772 KB n = 16
35 Correct 7 ms 12772 KB n = 16
36 Correct 7 ms 12756 KB n = 15
37 Correct 7 ms 12756 KB n = 8
38 Correct 8 ms 12756 KB n = 16
39 Correct 7 ms 12756 KB n = 16
40 Correct 6 ms 12756 KB n = 9
41 Correct 7 ms 12756 KB n = 16
42 Correct 7 ms 12776 KB n = 16
43 Correct 7 ms 12776 KB n = 16
44 Correct 8 ms 12780 KB n = 9
45 Correct 7 ms 12736 KB n = 15
46 Correct 7 ms 12780 KB n = 16
47 Correct 7 ms 12756 KB n = 16
48 Correct 7 ms 12832 KB n = 16
49 Correct 405 ms 45512 KB n = 199999
50 Correct 369 ms 45384 KB n = 199991
51 Correct 392 ms 45344 KB n = 199993
52 Correct 257 ms 39448 KB n = 152076
53 Correct 148 ms 28264 KB n = 93249
54 Correct 300 ms 40020 KB n = 199910
55 Correct 304 ms 42876 KB n = 199999
56 Correct 297 ms 40384 KB n = 199997
57 Correct 336 ms 40384 KB n = 171294
58 Correct 253 ms 38008 KB n = 140872
59 Correct 293 ms 42616 KB n = 199886
60 Correct 300 ms 46568 KB n = 199996
61 Correct 288 ms 43972 KB n = 200000
62 Correct 282 ms 48068 KB n = 199998
63 Correct 295 ms 47124 KB n = 200000
64 Correct 292 ms 48040 KB n = 199998
65 Correct 347 ms 51268 KB n = 200000
66 Correct 316 ms 49684 KB n = 190000
67 Correct 337 ms 47812 KB n = 177777
68 Correct 145 ms 30260 KB n = 100000
69 Correct 328 ms 48084 KB n = 200000
70 Correct 349 ms 43128 KB n = 200000
71 Correct 377 ms 51260 KB n = 200000
72 Correct 374 ms 49316 KB n = 200000
73 Correct 433 ms 49296 KB n = 200000
74 Correct 377 ms 49236 KB n = 200000
75 Correct 341 ms 51208 KB n = 200000
76 Correct 335 ms 51148 KB n = 200000
77 Correct 198 ms 37072 KB n = 200000
78 Correct 186 ms 32976 KB n = 200000
79 Correct 330 ms 44868 KB n = 184307
80 Correct 109 ms 27536 KB n = 76040
81 Correct 330 ms 42984 KB n = 199981
82 Correct 294 ms 46336 KB n = 199994
83 Correct 337 ms 43940 KB n = 199996
84 Correct 274 ms 48092 KB n = 199998
85 Correct 298 ms 47096 KB n = 200000
86 Correct 305 ms 47940 KB n = 199998
87 Correct 350 ms 51236 KB n = 200000
88 Correct 350 ms 51228 KB n = 200000
89 Correct 367 ms 51148 KB n = 200000
90 Correct 331 ms 47968 KB n = 200000
91 Correct 319 ms 43172 KB n = 200000
92 Correct 382 ms 51140 KB n = 200000