oj.uz

Submission #823521

# Submission time Handle Problem Language Result Execution time Memory
823521 2023-08-12T16:40:37 Z Sohsoh84 Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 181 ms 27580 KB 
#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)		(x).begin(), (x).end()
#define debug(x)	cerr << #x << ": " << x << endl;
#define sep		' '
#define X		first
#define Y		second

const ll MAXN = 1e6 + 10;
const ll INF = 1e9 + 7;

int n, cnt[MAXN], par[MAXN];
vector<int> comp_vec;

int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline bool unite(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return false;
	par[u] = v;
	
	return true;
}

inline int ind(int x) {
	return lower_bound(all(comp_vec), x) - comp_vec.begin();
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	s.push_back(0);
	t.push_back(1e9 + 7);

	ll ans = 0;
	for (int i = 0; i < int(s.size()); i++) {
		comp_vec.push_back(s[i]);
		comp_vec.push_back(t[i]);
	}

	sort(all(comp_vec));
	comp_vec.resize(unique(all(comp_vec)) - comp_vec.begin());

	for (int i = 0; i < int(s.size()); i++) {
		cnt[ind(s[i])]++;
		cnt[ind(t[i])]--;
	}

	int m = comp_vec.size();
	for (int i = 0; i < m; i++) par[i] = i;

	int tot = -1;
	vector<pair<int, pll>> edges;
	for (int i = 0; i < m - 1; i++) {
		tot += cnt[i];
		if (tot <= 0) {
			unite(i, i + 1);
		} else if (tot > 1) {
			unite(i, i + 1);
			ans += 1ll * (tot - 1) * (comp_vec[i + 1] - comp_vec[i]);
		}

		//cerr << tot << sep << comp_vec[i] << sep << ans << endl;
		edges.push_back({comp_vec[i + 1] - comp_vec[i], {i, i + 1}});
	}

	sort(all(edges));
	for (auto [x, e] : edges)
		if (unite(e.X, e.Y)){
		//	cerr << e.X << ' ' << e.Y << ' ' <<  x << endl;
			ans += x;
		}

	return ans/2;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 304 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 1 ms 212 KB answer is not correct: 352992301 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 304 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 1 ms 212 KB answer is not correct: 352992301 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 27456 KB n = 199999
2 Correct 167 ms 26692 KB n = 199991
3 Correct 166 ms 27580 KB n = 199993
4 Correct 118 ms 22692 KB n = 152076
5 Correct 71 ms 12996 KB n = 93249
6 Correct 153 ms 24140 KB n = 199910
7 Correct 158 ms 26480 KB n = 199999
8 Correct 181 ms 24204 KB n = 199997
9 Correct 161 ms 24020 KB n = 171294
10 Incorrect 120 ms 22328 KB answer is not correct: 1 instead of 0
11 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 304 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Incorrect 1 ms 212 KB answer is not correct: 352992301 instead of 523688153
7 Halted 0 ms 0 KB -