oj.uz

Submission #988937

# Submission time Handle Problem Language Result Execution time Memory
988937 2024-05-27T04:15:07 Z flappybird Swapping Cities (APIO20_swap) C++17
7 / 100
 330 ms 36580 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 (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 5 ms 14480 KB Output is correct
3 Correct 6 ms 14572 KB Output is correct
4 Correct 6 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 52 ms 28408 KB Output is correct
10 Correct 64 ms 31712 KB Output is correct
11 Correct 74 ms 31424 KB Output is correct
12 Correct 67 ms 32368 KB Output is correct
13 Correct 66 ms 30668 KB Output is correct
14 Correct 64 ms 28540 KB Output is correct
15 Correct 163 ms 33240 KB Output is correct
16 Correct 138 ms 32856 KB Output is correct
17 Correct 155 ms 33996 KB Output is correct
18 Correct 200 ms 32568 KB Output is correct
19 Incorrect 67 ms 19800 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 5 ms 14480 KB Output is correct
3 Correct 330 ms 32204 KB Output is correct
4 Correct 297 ms 36460 KB Output is correct
5 Correct 329 ms 36580 KB Output is correct
6 Correct 286 ms 36428 KB Output is correct
7 Correct 324 ms 36544 KB Output is correct
8 Correct 297 ms 35848 KB Output is correct
9 Correct 308 ms 36376 KB Output is correct
10 Correct 295 ms 35860 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 5 ms 14480 KB Output is correct
3 Correct 6 ms 14572 KB Output is correct
4 Correct 6 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 5 ms 14428 KB Output is correct
10 Incorrect 6 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 5 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14480 KB Output is correct
4 Correct 6 ms 14572 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 14684 KB Output is correct
9 Correct 6 ms 14684 KB Output is correct
10 Correct 52 ms 28408 KB Output is correct
11 Correct 64 ms 31712 KB Output is correct
12 Correct 74 ms 31424 KB Output is correct
13 Correct 67 ms 32368 KB Output is correct
14 Correct 66 ms 30668 KB Output is correct
15 Incorrect 6 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 5 ms 14480 KB Output is correct
3 Correct 6 ms 14572 KB Output is correct
4 Correct 6 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 52 ms 28408 KB Output is correct
10 Correct 64 ms 31712 KB Output is correct
11 Correct 74 ms 31424 KB Output is correct
12 Correct 67 ms 32368 KB Output is correct
13 Correct 66 ms 30668 KB Output is correct
14 Correct 64 ms 28540 KB Output is correct
15 Correct 163 ms 33240 KB Output is correct
16 Correct 138 ms 32856 KB Output is correct
17 Correct 155 ms 33996 KB Output is correct
18 Correct 200 ms 32568 KB Output is correct
19 Correct 330 ms 32204 KB Output is correct
20 Correct 297 ms 36460 KB Output is correct
21 Correct 329 ms 36580 KB Output is correct
22 Correct 286 ms 36428 KB Output is correct
23 Correct 324 ms 36544 KB Output is correct
24 Correct 297 ms 35848 KB Output is correct
25 Correct 308 ms 36376 KB Output is correct
26 Correct 295 ms 35860 KB Output is correct
27 Incorrect 6 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 5 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14480 KB Output is correct
4 Correct 6 ms 14572 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 14684 KB Output is correct
9 Correct 6 ms 14684 KB Output is correct
10 Correct 52 ms 28408 KB Output is correct
11 Correct 64 ms 31712 KB Output is correct
12 Correct 74 ms 31424 KB Output is correct
13 Correct 67 ms 32368 KB Output is correct
14 Correct 66 ms 30668 KB Output is correct
15 Correct 64 ms 28540 KB Output is correct
16 Correct 163 ms 33240 KB Output is correct
17 Correct 138 ms 32856 KB Output is correct
18 Correct 155 ms 33996 KB Output is correct
19 Correct 200 ms 32568 KB Output is correct
20 Correct 330 ms 32204 KB Output is correct
21 Correct 297 ms 36460 KB Output is correct
22 Correct 329 ms 36580 KB Output is correct
23 Correct 286 ms 36428 KB Output is correct
24 Correct 324 ms 36544 KB Output is correct
25 Correct 297 ms 35848 KB Output is correct
26 Correct 308 ms 36376 KB Output is correct
27 Correct 295 ms 35860 KB Output is correct
28 Incorrect 6 ms 14684 KB Output isn't correct
29 Halted 0 ms 0 KB -