oj.uz

답안 #241841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241841 2020-06-25T20:26:15 Z godwind Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 623 ms 70496 KB 
#include "railroad.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>

using namespace std;

template<typename T> void uin(T &a, T b) {
	if (b < a) a = b;
}

#define all(v) v.begin(), v.end()

const long long INF = 1e18 + 228;
const int OGO = 1000 * 1000 * 1000 + 228;
const int N = 400 * 1000 + 228;

long long dp[(1 << 17) + 17][16];

int p[N], siz[N];

void init(int n) {
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
		siz[i] = 1;
	}
}

int getp(int v) {
	if (v == p[v]) return v;
	p[v] = getp(p[v]);
	return p[v];
}

void join(int u, int v) {
	u = getp(u);
	v = getp(v);
	if (u != v) {
		if (siz[u] > siz[v]) swap(u, v);
		p[u] = v;
		siz[v] += siz[u];
	}
}

struct Edge
{
	int u, v, w;
	Edge() {}
	Edge(int _u, int _v, int _w) {
		u = _u;
		v = _v;
		w = _w;
	}
};
bool operator<(Edge A, Edge B) {
	return A.w < B.w;
}

vector<int> crd;
vector<int> g[N], gr[N];

int pref[N];
bool used[N];

void dfs(int v, int start) {
	join(v, start);
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to]) {
			dfs(to, start);
		}
	}
}

int Get(int i) {
	return lower_bound(all(crd), i) - crd.begin() + 1;
}

void AddEdge(int from, int to) {
	from = Get(from);
	to = Get(to);
	g[from].emplace_back(to);
	++pref[from];
	--pref[to];
	gr[from].emplace_back(to);
	gr[to].emplace_back(from);
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int)s.size();
	if (n <= -15) {
		for (int i = 0; i < (1 << n); ++i) {
			for (int j = 0; j < n; ++j) {
				dp[i][j] = INF;
			}
		}
		for (int fir = 0; fir < n; ++fir) {
			dp[1 << fir][fir] = 0;
		}
		for (int mask = 0; mask < (1 << n); ++mask) {
			for (int last = 0; last < n; ++last) {
				if (dp[mask][last] != INF) {
					for (int new_last = 0; new_last < n; ++new_last) {
						if ((mask >> new_last) & 1) continue;
						long long cur = dp[mask][last] + max(0, t[last] - s[new_last]);
						uin(dp[mask | (1 << new_last)][new_last], cur);
					}
				}
			}
		}
		long long answer = INF;
		for (int last = 0; last < n; ++last) {
			uin(answer, dp[(1 << n) - 1][last]);
		}
		return answer;
	} else {
		// subtask 3
		crd.clear();
		for (int i = 0; i < n; ++i) {
			crd.emplace_back(s[i]);
			crd.emplace_back(t[i]);
		}
		crd.emplace_back(OGO);
		sort(crd.begin(), crd.end());
		crd.erase(unique(crd.begin(), crd.end()), crd.end());
		int sz = (int)crd.size();
		for (int i = 0; i < n; ++i) {
			AddEdge(s[i], t[i]);
		}
		AddEdge(OGO, 1);
		long long answer = 0;
		vector< Edge > edges;
		for (int i = 1; i < sz; ++i) {
			pref[i] += pref[i - 1];
			if (pref[i] > 0) {
				answer += (long long)pref[i] * (long long)(crd[i] - crd[i - 1]);
				gr[i].emplace_back(i + 1);
				gr[i + 1].emplace_back(i);
			} else {
				if (pref[i] != 0) {
					gr[i].emplace_back(i + 1);
					gr[i + 1].emplace_back(i);
				}
			}
			edges.emplace_back( i, i + 1, crd[i] - crd[i - 1] );
		}
		sort(all(edges));
		int comps = 0;
		init(sz);
		for (int i = 1; i <= sz; ++i) {
			if (!used[i]) {
				dfs(i, i);
			}
		}
		for (auto e : edges) {
			int u = e.u, v = e.v, w = e.w;
			if (getp(u) != getp(v)) {
				answer += w;
				join(u, v);
			}
		}
		return answer;
	}
    return 0;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:157:7: warning: unused variable 'comps' [-Wunused-variable]
   int comps = 0;
       ^~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19072 KB n = 2
2 Correct 17 ms 19072 KB n = 2
3 Correct 17 ms 19200 KB n = 2
4 Correct 15 ms 19200 KB n = 2
5 Correct 16 ms 19072 KB n = 2
6 Correct 17 ms 19200 KB n = 2
7 Correct 16 ms 19072 KB n = 3
8 Correct 16 ms 19072 KB n = 3
9 Correct 17 ms 19072 KB n = 3
10 Correct 15 ms 19200 KB n = 8
11 Correct 15 ms 19072 KB n = 8
12 Correct 18 ms 19200 KB n = 8
13 Correct 16 ms 19072 KB n = 8
14 Correct 16 ms 19200 KB n = 8
15 Correct 17 ms 19200 KB n = 8
16 Correct 17 ms 19072 KB n = 8
17 Correct 15 ms 19072 KB n = 8
18 Correct 17 ms 19072 KB n = 8
19 Correct 17 ms 19328 KB n = 3
20 Correct 15 ms 19200 KB n = 7
21 Correct 17 ms 19072 KB n = 8
22 Correct 15 ms 19072 KB n = 8
23 Correct 15 ms 19200 KB n = 8
24 Correct 17 ms 19200 KB n = 8
25 Correct 17 ms 19200 KB n = 8

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 63460 KB n = 199999
2 Correct 554 ms 63580 KB n = 199991
3 Correct 622 ms 63508 KB n = 199993
4 Correct 445 ms 53596 KB n = 152076
5 Correct 233 ms 40036 KB n = 93249
6 Correct 438 ms 54268 KB n = 199910
7 Correct 488 ms 60380 KB n = 199999
8 Correct 416 ms 55008 KB n = 199997
9 Correct 459 ms 57436 KB n = 171294
10 Correct 376 ms 50912 KB n = 140872
11 Correct 450 ms 54752 KB n = 199886
12 Correct 485 ms 60764 KB n = 199996
13 Correct 440 ms 56668 KB n = 200000
14 Correct 467 ms 63328 KB n = 199998
15 Correct 428 ms 61792 KB n = 200000
16 Correct 439 ms 62812 KB n = 199998
17 Correct 533 ms 66524 KB n = 200000
18 Correct 530 ms 64220 KB n = 190000
19 Correct 498 ms 61408 KB n = 177777
20 Correct 243 ms 40292 KB n = 100000
21 Correct 514 ms 61404 KB n = 200000
22 Correct 509 ms 53980 KB n = 200000
23 Correct 562 ms 66528 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19072 KB n = 2
2 Correct 17 ms 19072 KB n = 2
3 Correct 17 ms 19200 KB n = 2
4 Correct 15 ms 19200 KB n = 2
5 Correct 16 ms 19072 KB n = 2
6 Correct 17 ms 19200 KB n = 2
7 Correct 16 ms 19072 KB n = 3
8 Correct 16 ms 19072 KB n = 3
9 Correct 17 ms 19072 KB n = 3
10 Correct 15 ms 19200 KB n = 8
11 Correct 15 ms 19072 KB n = 8
12 Correct 18 ms 19200 KB n = 8
13 Correct 16 ms 19072 KB n = 8
14 Correct 16 ms 19200 KB n = 8
15 Correct 17 ms 19200 KB n = 8
16 Correct 17 ms 19072 KB n = 8
17 Correct 15 ms 19072 KB n = 8
18 Correct 17 ms 19072 KB n = 8
19 Correct 17 ms 19328 KB n = 3
20 Correct 15 ms 19200 KB n = 7
21 Correct 17 ms 19072 KB n = 8
22 Correct 15 ms 19072 KB n = 8
23 Correct 15 ms 19200 KB n = 8
24 Correct 17 ms 19200 KB n = 8
25 Correct 17 ms 19200 KB n = 8
26 Correct 17 ms 19200 KB n = 8
27 Correct 16 ms 19072 KB n = 8
28 Correct 16 ms 19072 KB n = 8
29 Correct 15 ms 19072 KB n = 16
30 Correct 15 ms 19072 KB n = 16
31 Correct 16 ms 19200 KB n = 16
32 Correct 17 ms 19072 KB n = 16
33 Correct 17 ms 19200 KB n = 16
34 Correct 17 ms 19328 KB n = 16
35 Correct 16 ms 19072 KB n = 16
36 Correct 15 ms 19072 KB n = 15
37 Correct 17 ms 19200 KB n = 8
38 Correct 16 ms 19200 KB n = 16
39 Correct 15 ms 19200 KB n = 16
40 Correct 17 ms 19072 KB n = 9
41 Correct 17 ms 19200 KB n = 16
42 Correct 16 ms 19200 KB n = 16
43 Correct 16 ms 19200 KB n = 16
44 Correct 15 ms 19072 KB n = 9
45 Correct 17 ms 19072 KB n = 15
46 Correct 17 ms 19200 KB n = 16
47 Correct 16 ms 19072 KB n = 16
48 Correct 16 ms 19072 KB n = 16
49 Correct 567 ms 63460 KB n = 199999
50 Correct 554 ms 63580 KB n = 199991
51 Correct 622 ms 63508 KB n = 199993
52 Correct 445 ms 53596 KB n = 152076
53 Correct 233 ms 40036 KB n = 93249
54 Correct 438 ms 54268 KB n = 199910
55 Correct 488 ms 60380 KB n = 199999
56 Correct 416 ms 55008 KB n = 199997
57 Correct 459 ms 57436 KB n = 171294
58 Correct 376 ms 50912 KB n = 140872
59 Correct 450 ms 54752 KB n = 199886
60 Correct 485 ms 60764 KB n = 199996
61 Correct 440 ms 56668 KB n = 200000
62 Correct 467 ms 63328 KB n = 199998
63 Correct 428 ms 61792 KB n = 200000
64 Correct 439 ms 62812 KB n = 199998
65 Correct 533 ms 66524 KB n = 200000
66 Correct 530 ms 64220 KB n = 190000
67 Correct 498 ms 61408 KB n = 177777
68 Correct 243 ms 40292 KB n = 100000
69 Correct 514 ms 61404 KB n = 200000
70 Correct 509 ms 53980 KB n = 200000
71 Correct 562 ms 66528 KB n = 200000
72 Correct 559 ms 67552 KB n = 200000
73 Correct 565 ms 67420 KB n = 200000
74 Correct 557 ms 67300 KB n = 200000
75 Correct 528 ms 70368 KB n = 200000
76 Correct 551 ms 70496 KB n = 200000
77 Correct 368 ms 52964 KB n = 200000
78 Correct 333 ms 46820 KB n = 200000
79 Correct 540 ms 61788 KB n = 184307
80 Correct 184 ms 37732 KB n = 76040
81 Correct 459 ms 57824 KB n = 199981
82 Correct 465 ms 64092 KB n = 199994
83 Correct 431 ms 59492 KB n = 199996
84 Correct 431 ms 66396 KB n = 199998
85 Correct 437 ms 64988 KB n = 200000
86 Correct 481 ms 66140 KB n = 199998
87 Correct 516 ms 70364 KB n = 200000
88 Correct 533 ms 70368 KB n = 200000
89 Correct 525 ms 70368 KB n = 200000
90 Correct 505 ms 65248 KB n = 200000
91 Correct 530 ms 57848 KB n = 200000
92 Correct 623 ms 70344 KB n = 200000