oj.uz

Submission #988935

# Submission time Handle Problem Language Result Execution time Memory
988935 2024-05-27T04:13:28 Z flappybird Swapping Cities (APIO20_swap) C++17
0 / 100
 300 ms 37680 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[v] = min(val[v], 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 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 7 ms 14760 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14624 KB Output is correct
9 Correct 59 ms 30044 KB Output is correct
10 Correct 65 ms 33484 KB Output is correct
11 Correct 72 ms 33236 KB Output is correct
12 Correct 71 ms 34512 KB Output is correct
13 Correct 68 ms 32732 KB Output is correct
14 Correct 69 ms 30424 KB Output is correct
15 Correct 150 ms 36832 KB Output is correct
16 Correct 143 ms 36368 KB Output is correct
17 Correct 145 ms 37680 KB Output is correct
18 Correct 188 ms 36412 KB Output is correct
19 Incorrect 67 ms 21484 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Incorrect 300 ms 31688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 7 ms 14760 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14624 KB Output is correct
9 Correct 5 ms 14428 KB Output is correct
10 Incorrect 5 ms 14680 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 6 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 8 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 7 ms 14760 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 6 ms 14624 KB Output is correct
10 Correct 59 ms 30044 KB Output is correct
11 Correct 65 ms 33484 KB Output is correct
12 Correct 72 ms 33236 KB Output is correct
13 Correct 71 ms 34512 KB Output is correct
14 Correct 68 ms 32732 KB Output is correct
15 Incorrect 5 ms 14680 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 7 ms 14760 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 6 ms 14624 KB Output is correct
9 Correct 59 ms 30044 KB Output is correct
10 Correct 65 ms 33484 KB Output is correct
11 Correct 72 ms 33236 KB Output is correct
12 Correct 71 ms 34512 KB Output is correct
13 Correct 68 ms 32732 KB Output is correct
14 Correct 69 ms 30424 KB Output is correct
15 Correct 150 ms 36832 KB Output is correct
16 Correct 143 ms 36368 KB Output is correct
17 Correct 145 ms 37680 KB Output is correct
18 Correct 188 ms 36412 KB Output is correct
19 Incorrect 300 ms 31688 KB Output isn't correct
20 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 6 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 8 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 7 ms 14760 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 6 ms 14624 KB Output is correct
10 Correct 59 ms 30044 KB Output is correct
11 Correct 65 ms 33484 KB Output is correct
12 Correct 72 ms 33236 KB Output is correct
13 Correct 71 ms 34512 KB Output is correct
14 Correct 68 ms 32732 KB Output is correct
15 Correct 69 ms 30424 KB Output is correct
16 Correct 150 ms 36832 KB Output is correct
17 Correct 143 ms 36368 KB Output is correct
18 Correct 145 ms 37680 KB Output is correct
19 Correct 188 ms 36412 KB Output is correct
20 Incorrect 300 ms 31688 KB Output isn't correct
21 Halted 0 ms 0 KB -