oj.uz

Submission #302418

# Submission time Handle Problem Language Result Execution time Memory
302418 2020-09-18T16:33:18 Z JPN20 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 594 ms 99680 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

// Input
long long N;
long long S[1 << 18], T[1 << 18];
long long dp[1 << 16][16];

// Graph
bool used[1 << 19];
int cnt[1 << 19];
int col[1 << 19], cntv;
vector<int> ord;
vector<int> X[1 << 19];
vector<int> Y[1 << 19];

class UnionFind {
	public:
	vector<int> par;
	
	void init(int sz) {
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u);
		v = root(v);
		if (u != v) par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

void dfs1(int pos) {
	used[pos] = true;
	for (int i : X[pos]) {
		if (used[i] == true) continue;
		dfs1(i);
	}
	ord.push_back(pos);
}

void dfs2(int pos) {
	col[pos] = cntv;
	for (int i : Y[pos]) {
		if (col[i] >= 1) continue;
		dfs2(i);
	}
}

long long solve_subtask4() {
	long long FinalAns = 0;
	
	// ZAATS
	vector<long long> vec;
	vec.push_back(0);
	vec.push_back(1000000007);
	for (int i = 0; i < N; i++) vec.push_back(S[i]);
	for (int i = 0; i < N; i++) vec.push_back(T[i]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for (int i = 0; i < N; i++) S[i] = lower_bound(vec.begin(), vec.end(), S[i]) - vec.begin();
	for (int i = 0; i < N; i++) T[i] = lower_bound(vec.begin(), vec.end(), T[i]) - vec.begin();
	
	// GRAPH
	cnt[0] += 1;
	cnt[vec.size() - 1] -= 1;
	X[vec.size() - 1].push_back(0);
	Y[0].push_back(vec.size() - 1);
	for (int i = 0; i < N; i++) X[S[i]].push_back(T[i]);
	for (int i = 0; i < N; i++) Y[T[i]].push_back(S[i]);
	for (int i = 0; i < N; i++) cnt[S[i]] -= 1;
	for (int i = 0; i < N; i++) cnt[T[i]] += 1;
	
	// HANTE
	for (int i = 1; i < (int)vec.size(); i++) cnt[i] += cnt[i - 1];
	for (int i = 0; i < (int)vec.size(); i++) {
		if (cnt[i] <= -1) {
			FinalAns -= 1LL * cnt[i] * (long long)(vec[i + 1] - vec[i]);
			X[i + 1].push_back(i);
			Y[i].push_back(i + 1);
		}
		if (cnt[i] >= 1) {
			X[i].push_back(i + 1);
			Y[i + 1].push_back(i);
		}
	}
	
	// SCC
	for (int i = 0; i < (int)vec.size(); i++) {
		if (used[i] == true) continue;
		dfs1(i);
	}
	for (int i = ord.size() - 1; i >= 0; i--) {
		if (col[ord[i]] >= 1) continue;
		cntv++;
		dfs2(ord[i]);
	}
	
	// PRFNL
	vector<tuple<long long, int, int>> tup;
	for (int i = 0; i < (int)vec.size() - 1; i++) {
		if (cnt[i] >= 1) continue;
		tup.push_back(make_tuple(vec[i + 1] - vec[i], col[i], col[i + 1]));
	}
	sort(tup.begin(), tup.end());
	
	// FINAL
	UnionFind UF; UF.init(vec.size() + 2);
	for (int i = 0; i < (int)tup.size(); i++) {
		long long cost = get<0>(tup[i]), a1 = get<1>(tup[i]), a2 = get<2>(tup[i]);
		if (UF.same(a1, a2) == false) {
			UF.unite(a1, a2);
			FinalAns += cost;
		}
	}
	return FinalAns;
}

long long solve_subtask2() {
	// PRCLC
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < N; j++) dp[i][j] = (1LL << 60);
	}
	for (int i = 0; i < N; i++) dp[1 << i][i] = 0;
	
	// CALC
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < N; j++) {
			if (dp[i][j] == (1LL << 60)) continue;
			for (int k = 0; k < N; k++) {
				if ((i / (1 << k)) % 2 == 1) continue;
				long long cost = max(0LL, T[j] - S[k]);
				dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + cost);
			}
		}
	}
	
	// FINAL
	long long Answer = (1LL << 60);
	for (int i = 0; i < N; i++) Answer = min(Answer, dp[(1 << N) - 1][i]);
	return Answer;
}

int cnts = 0;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	N = s.size();
	for (int i = 0; i < N; i++) S[i] = s[i];
	for (int i = 0; i < N; i++) T[i] = t[i];
	cnts += 1;
	
	return solve_subtask4();
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 85848 KB n = 199999
2 Correct 594 ms 85472 KB n = 199991
3 Correct 533 ms 95356 KB n = 199993
4 Correct 390 ms 63356 KB n = 152076
5 Correct 224 ms 48616 KB n = 93249
6 Correct 455 ms 66372 KB n = 199910
7 Correct 481 ms 75432 KB n = 199999
8 Correct 496 ms 69284 KB n = 199997
9 Correct 492 ms 68192 KB n = 171294
10 Correct 361 ms 60512 KB n = 140872
11 Correct 457 ms 67424 KB n = 199886
12 Correct 490 ms 77536 KB n = 199996
13 Correct 486 ms 72672 KB n = 200000
14 Correct 498 ms 84916 KB n = 199998
15 Correct 511 ms 82228 KB n = 200000
16 Correct 503 ms 82912 KB n = 199998
17 Correct 463 ms 87264 KB n = 200000
18 Correct 475 ms 80092 KB n = 190000
19 Correct 363 ms 79840 KB n = 177777
20 Correct 261 ms 50792 KB n = 100000
21 Correct 542 ms 75616 KB n = 200000
22 Correct 490 ms 72804 KB n = 200000
23 Correct 564 ms 91744 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24960 KB n = 2
2 Correct 18 ms 24960 KB n = 2
3 Correct 18 ms 24960 KB n = 2
4 Correct 17 ms 24960 KB n = 2
5 Correct 18 ms 24960 KB n = 2
6 Correct 18 ms 25088 KB n = 2
7 Correct 17 ms 24960 KB n = 3
8 Correct 17 ms 24960 KB n = 3
9 Correct 17 ms 24960 KB n = 3
10 Correct 17 ms 24960 KB n = 8
11 Correct 17 ms 24960 KB n = 8
12 Correct 18 ms 24960 KB n = 8
13 Correct 18 ms 24960 KB n = 8
14 Correct 17 ms 24960 KB n = 8
15 Correct 17 ms 24960 KB n = 8
16 Correct 18 ms 24936 KB n = 8
17 Correct 17 ms 24960 KB n = 8
18 Correct 18 ms 24960 KB n = 8
19 Correct 17 ms 24960 KB n = 3
20 Correct 17 ms 24960 KB n = 7
21 Correct 17 ms 24960 KB n = 8
22 Correct 17 ms 24960 KB n = 8
23 Correct 18 ms 24960 KB n = 8
24 Correct 17 ms 24960 KB n = 8
25 Correct 17 ms 24960 KB n = 8
26 Correct 18 ms 24960 KB n = 8
27 Correct 17 ms 24960 KB n = 8
28 Correct 17 ms 24960 KB n = 8
29 Correct 17 ms 24960 KB n = 16
30 Correct 17 ms 24960 KB n = 16
31 Correct 18 ms 24960 KB n = 16
32 Correct 18 ms 24960 KB n = 16
33 Correct 17 ms 24960 KB n = 16
34 Correct 18 ms 25088 KB n = 16
35 Correct 18 ms 24960 KB n = 16
36 Correct 17 ms 24960 KB n = 15
37 Correct 17 ms 24960 KB n = 8
38 Correct 18 ms 24960 KB n = 16
39 Correct 17 ms 24960 KB n = 16
40 Correct 18 ms 24960 KB n = 9
41 Correct 17 ms 24960 KB n = 16
42 Correct 18 ms 24960 KB n = 16
43 Correct 17 ms 24992 KB n = 16
44 Correct 16 ms 24960 KB n = 9
45 Correct 18 ms 24960 KB n = 15
46 Correct 17 ms 24960 KB n = 16
47 Correct 16 ms 24960 KB n = 16
48 Correct 17 ms 24960 KB n = 16
49 Correct 503 ms 85848 KB n = 199999
50 Correct 594 ms 85472 KB n = 199991
51 Correct 533 ms 95356 KB n = 199993
52 Correct 390 ms 63356 KB n = 152076
53 Correct 224 ms 48616 KB n = 93249
54 Correct 455 ms 66372 KB n = 199910
55 Correct 481 ms 75432 KB n = 199999
56 Correct 496 ms 69284 KB n = 199997
57 Correct 492 ms 68192 KB n = 171294
58 Correct 361 ms 60512 KB n = 140872
59 Correct 457 ms 67424 KB n = 199886
60 Correct 490 ms 77536 KB n = 199996
61 Correct 486 ms 72672 KB n = 200000
62 Correct 498 ms 84916 KB n = 199998
63 Correct 511 ms 82228 KB n = 200000
64 Correct 503 ms 82912 KB n = 199998
65 Correct 463 ms 87264 KB n = 200000
66 Correct 475 ms 80092 KB n = 190000
67 Correct 363 ms 79840 KB n = 177777
68 Correct 261 ms 50792 KB n = 100000
69 Correct 542 ms 75616 KB n = 200000
70 Correct 490 ms 72804 KB n = 200000
71 Correct 564 ms 91744 KB n = 200000
72 Correct 484 ms 88544 KB n = 200000
73 Correct 577 ms 79072 KB n = 200000
74 Correct 535 ms 97120 KB n = 200000
75 Correct 480 ms 99680 KB n = 200000
76 Correct 415 ms 89184 KB n = 200000
77 Correct 397 ms 63840 KB n = 200000
78 Correct 327 ms 60768 KB n = 200000
79 Correct 493 ms 72160 KB n = 184307
80 Correct 181 ms 45544 KB n = 76040
81 Correct 453 ms 69344 KB n = 199981
82 Correct 494 ms 79540 KB n = 199994
83 Correct 461 ms 74720 KB n = 199996
84 Correct 493 ms 87008 KB n = 199998
85 Correct 493 ms 84192 KB n = 200000
86 Correct 497 ms 85344 KB n = 199998
87 Correct 474 ms 90208 KB n = 200000
88 Correct 506 ms 85984 KB n = 200000
89 Correct 440 ms 89288 KB n = 200000
90 Correct 540 ms 78432 KB n = 200000
91 Correct 470 ms 75620 KB n = 200000
92 Correct 546 ms 94432 KB n = 200000