oj.uz

Submission #260009

# Submission time Handle Problem Language Result Execution time Memory
260009 2020-08-08T22:43:51 Z ant101 Roller Coaster Railroad (IOI16_railroad) C++14
41 / 100
 527 ms 61216 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];
 
vector<int> crd;
vector<int> g[N], gr[N];
 
int pref[N];
bool used[N];
 
 
void dfs(int v) {
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to]) {
			dfs(to);
		}
	}
}
 
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);
		for (int i = 1; i < sz; ++i) {
			pref[i] += pref[i - 1];
			if (pref[i] > 0) {
				return 10;
			}
			if (pref[i] != 0) {
				gr[i].emplace_back(i + 1);
				gr[i + 1].emplace_back(i);
			}
		}
		int comps = 0;
		for (int i = 1; i <= sz; ++i) {
			if (!used[i]) {
				dfs(i);
				++comps;
			}
		}
		if (comps > 1) {
			return 20;
		} else {
			return 0;
		}
 
	}
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB n = 2
2 Correct 13 ms 19072 KB n = 2
3 Correct 12 ms 19072 KB n = 2
4 Correct 14 ms 19072 KB n = 2
5 Correct 12 ms 19072 KB n = 2
6 Correct 13 ms 19072 KB n = 2
7 Correct 12 ms 19072 KB n = 3
8 Correct 13 ms 19072 KB n = 3
9 Correct 12 ms 19072 KB n = 3
10 Correct 12 ms 19200 KB n = 8
11 Correct 12 ms 19200 KB n = 8
12 Correct 14 ms 19200 KB n = 8
13 Correct 13 ms 19200 KB n = 8
14 Correct 12 ms 19200 KB n = 8
15 Correct 12 ms 19200 KB n = 8
16 Correct 13 ms 19200 KB n = 8
17 Correct 12 ms 19200 KB n = 8
18 Correct 13 ms 19200 KB n = 8
19 Correct 12 ms 19072 KB n = 3
20 Correct 12 ms 19200 KB n = 7
21 Correct 13 ms 19200 KB n = 8
22 Correct 12 ms 19200 KB n = 8
23 Correct 13 ms 19200 KB n = 8
24 Correct 14 ms 19200 KB n = 8
25 Correct 14 ms 19200 KB n = 8
26 Correct 12 ms 19200 KB n = 8
27 Correct 13 ms 19104 KB n = 8
28 Correct 13 ms 19200 KB n = 8
29 Correct 13 ms 19072 KB n = 16
30 Correct 13 ms 19072 KB n = 16
31 Incorrect 14 ms 19072 KB answer is not correct: 10 instead of 5295826283
32 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 58132 KB n = 199999
2 Correct 400 ms 48188 KB n = 199991
3 Correct 378 ms 48104 KB n = 199993
4 Correct 374 ms 48616 KB n = 152076
5 Correct 205 ms 37228 KB n = 93249
6 Correct 414 ms 49384 KB n = 199910
7 Correct 418 ms 54248 KB n = 199999
8 Correct 399 ms 50152 KB n = 199997
9 Correct 446 ms 52200 KB n = 171294
10 Correct 345 ms 46472 KB n = 140872
11 Correct 414 ms 49768 KB n = 199886
12 Correct 422 ms 54632 KB n = 199996
13 Correct 414 ms 51432 KB n = 200000
14 Correct 310 ms 46952 KB n = 199998
15 Correct 326 ms 46840 KB n = 200000
16 Correct 322 ms 47464 KB n = 199998
17 Correct 368 ms 48256 KB n = 200000
18 Correct 354 ms 46568 KB n = 190000
19 Correct 425 ms 56392 KB n = 177777
20 Correct 203 ms 37484 KB n = 100000
21 Correct 451 ms 56140 KB n = 200000
22 Correct 434 ms 48488 KB n = 200000
23 Correct 527 ms 61216 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19072 KB n = 2
2 Correct 13 ms 19072 KB n = 2
3 Correct 12 ms 19072 KB n = 2
4 Correct 14 ms 19072 KB n = 2
5 Correct 12 ms 19072 KB n = 2
6 Correct 13 ms 19072 KB n = 2
7 Correct 12 ms 19072 KB n = 3
8 Correct 13 ms 19072 KB n = 3
9 Correct 12 ms 19072 KB n = 3
10 Correct 12 ms 19200 KB n = 8
11 Correct 12 ms 19200 KB n = 8
12 Correct 14 ms 19200 KB n = 8
13 Correct 13 ms 19200 KB n = 8
14 Correct 12 ms 19200 KB n = 8
15 Correct 12 ms 19200 KB n = 8
16 Correct 13 ms 19200 KB n = 8
17 Correct 12 ms 19200 KB n = 8
18 Correct 13 ms 19200 KB n = 8
19 Correct 12 ms 19072 KB n = 3
20 Correct 12 ms 19200 KB n = 7
21 Correct 13 ms 19200 KB n = 8
22 Correct 12 ms 19200 KB n = 8
23 Correct 13 ms 19200 KB n = 8
24 Correct 14 ms 19200 KB n = 8
25 Correct 14 ms 19200 KB n = 8
26 Correct 12 ms 19200 KB n = 8
27 Correct 13 ms 19104 KB n = 8
28 Correct 13 ms 19200 KB n = 8
29 Correct 13 ms 19072 KB n = 16
30 Correct 13 ms 19072 KB n = 16
31 Incorrect 14 ms 19072 KB answer is not correct: 10 instead of 5295826283
32 Halted 0 ms 0 KB -