oj.uz

Submission #988939

# Submission time Handle Problem Language Result Execution time Memory
988939 2024-05-27T04:17:45 Z flappybird Swapping Cities (APIO20_swap) C++17
7 / 100
 354 ms 33996 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define MAX 201010
using namespace std;
typedef pair<int, int> pii;
pii edges[MAX];
int W[MAX];

vector<pii> p[MAX];
vector<pii> numv[MAX];
vector<pii> nume[MAX];
int deg[MAX];
int val[MAX];
int rnk[MAX];

int N, M;

int find(int v, int t) {
	int loc = lower_bound(p[v].begin(), p[v].end(), pii(t + 1, -2)) - p[v].begin();
	loc--;
	return p[v][loc].second;
}

int getnumv(int v, int t) {
	int loc = lower_bound(numv[v].begin(), numv[v].end(), pii(t + 1, -2)) - numv[v].begin();
	loc--;
	return numv[v][loc].second;
}

int getnume(int v, int t) {
	int loc = lower_bound(nume[v].begin(), nume[v].end(), pii(t + 1, -2)) - nume[v].begin();
	loc--;
	return nume[v][loc].second;
}

void uni(int u, int v, int t) {
	deg[u]++;
	deg[v]++;
	int mx = max(deg[u], deg[v]);
	u = find(u, t);
	v = find(v, t);
	if (rnk[u] < rnk[v]) swap(u, v);
	if (u == v) nume[v].emplace_back(t, nume[v].back().second + 1);
	else {
		if (rnk[u] == rnk[v]) rnk[u]++;
		p[v].emplace_back(t, u);
		numv[u].emplace_back(t, numv[v].back().second + numv[u].back().second);
		nume[u].emplace_back(t, nume[v].back().second + nume[u].back().second + 1);
		if (val[v] <= t) val[u] = min(val[u], t);
	}
	if (mx > 2) val[u] = min(val[u], t);
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> _W) {
	N = _N;
	M = _M;
	int i;
	vector<int> v;
	for (i = 0; i < M; i++) v.push_back(i);
	sort(v.begin(), v.end(), [&](int i, int j) {return _W[i] < _W[j]; });
	i = 0;
	for (auto x : v) {
		edges[i] = pii(U[x], V[x]);
		W[i] = _W[x];
		i++;
	}
	for (i = 0; i < N; i++) p[i].emplace_back(-1, i), nume[i].emplace_back(-1, 0), numv[i].emplace_back(-1, 1), val[i] = M;
	for (i = 0; i < M; i++) {
		uni(edges[i].first, edges[i].second, i);
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int l, r;
	l = -1, r = M;
	while (r - l > 1) {
		int m = (l + r + 2) >> 1;
		m--;
		int x = find(X, m);
		int y = find(Y, m);
		if (x != y) {
			l = m;
			continue;
		}
		if (getnumv(x, m) <= getnume(x, m)) r = m;
		else if (val[x] <= m) r = m;
		else l = m;
	}
	if (r == M) return -1;
	return W[r];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 7 ms 14600 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 7 ms 14712 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 5 ms 14684 KB Output is correct
8 Correct 6 ms 14680 KB Output is correct
9 Correct 72 ms 28616 KB Output is correct
10 Correct 75 ms 31724 KB Output is correct
11 Correct 65 ms 31432 KB Output is correct
12 Correct 67 ms 32420 KB Output is correct
13 Correct 57 ms 30572 KB Output is correct
14 Correct 61 ms 28620 KB Output is correct
15 Correct 155 ms 33240 KB Output is correct
16 Correct 137 ms 32772 KB Output is correct
17 Correct 163 ms 33996 KB Output is correct
18 Correct 203 ms 32564 KB Output is correct
19 Incorrect 67 ms 19796 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 7 ms 14600 KB Output is correct
3 Correct 296 ms 32108 KB Output is correct
4 Correct 310 ms 32804 KB Output is correct
5 Correct 354 ms 32484 KB Output is correct
6 Correct 310 ms 32724 KB Output is correct
7 Correct 298 ms 32708 KB Output is correct
8 Correct 314 ms 31992 KB Output is correct
9 Correct 305 ms 32452 KB Output is correct
10 Correct 304 ms 32024 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 7 ms 14600 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 7 ms 14712 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 5 ms 14684 KB Output is correct
8 Correct 6 ms 14680 KB Output is correct
9 Correct 6 ms 14424 KB Output is correct
10 Incorrect 5 ms 14684 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 7 ms 14600 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 7 ms 14712 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 5 ms 14684 KB Output is correct
9 Correct 6 ms 14680 KB Output is correct
10 Correct 72 ms 28616 KB Output is correct
11 Correct 75 ms 31724 KB Output is correct
12 Correct 65 ms 31432 KB Output is correct
13 Correct 67 ms 32420 KB Output is correct
14 Correct 57 ms 30572 KB Output is correct
15 Incorrect 5 ms 14684 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 7 ms 14600 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 7 ms 14712 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 5 ms 14684 KB Output is correct
8 Correct 6 ms 14680 KB Output is correct
9 Correct 72 ms 28616 KB Output is correct
10 Correct 75 ms 31724 KB Output is correct
11 Correct 65 ms 31432 KB Output is correct
12 Correct 67 ms 32420 KB Output is correct
13 Correct 57 ms 30572 KB Output is correct
14 Correct 61 ms 28620 KB Output is correct
15 Correct 155 ms 33240 KB Output is correct
16 Correct 137 ms 32772 KB Output is correct
17 Correct 163 ms 33996 KB Output is correct
18 Correct 203 ms 32564 KB Output is correct
19 Correct 296 ms 32108 KB Output is correct
20 Correct 310 ms 32804 KB Output is correct
21 Correct 354 ms 32484 KB Output is correct
22 Correct 310 ms 32724 KB Output is correct
23 Correct 298 ms 32708 KB Output is correct
24 Correct 314 ms 31992 KB Output is correct
25 Correct 305 ms 32452 KB Output is correct
26 Correct 304 ms 32024 KB Output is correct
27 Incorrect 5 ms 14684 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 7 ms 14600 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 7 ms 14712 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 5 ms 14684 KB Output is correct
9 Correct 6 ms 14680 KB Output is correct
10 Correct 72 ms 28616 KB Output is correct
11 Correct 75 ms 31724 KB Output is correct
12 Correct 65 ms 31432 KB Output is correct
13 Correct 67 ms 32420 KB Output is correct
14 Correct 57 ms 30572 KB Output is correct
15 Correct 61 ms 28620 KB Output is correct
16 Correct 155 ms 33240 KB Output is correct
17 Correct 137 ms 32772 KB Output is correct
18 Correct 163 ms 33996 KB Output is correct
19 Correct 203 ms 32564 KB Output is correct
20 Correct 296 ms 32108 KB Output is correct
21 Correct 310 ms 32804 KB Output is correct
22 Correct 354 ms 32484 KB Output is correct
23 Correct 310 ms 32724 KB Output is correct
24 Correct 298 ms 32708 KB Output is correct
25 Correct 314 ms 31992 KB Output is correct
26 Correct 305 ms 32452 KB Output is correct
27 Correct 304 ms 32024 KB Output is correct
28 Incorrect 5 ms 14684 KB Output isn't correct
29 Halted 0 ms 0 KB -