oj.uz

Submission #988932

# Submission time Handle Problem Language Result Execution time Memory
988932 2024-05-27T04:03:21 Z flappybird Swapping Cities (APIO20_swap) C++17
0 / 100
 289 ms 42136 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];
vector<pii> deg[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;
}

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

void uni(int u, int v, int t) {
	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);
	}
}

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), deg[i].emplace_back(-1, 0);
	for (i = 0; i < M; i++) {
		uni(edges[i].first, edges[i].second, i);
		deg[edges[i].first].emplace_back(i, deg[edges[i].first].back().second + 1);
		deg[edges[i].second].emplace_back(i, deg[edges[i].second].back().second + 1);
	}
}

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 (getdeg(X, m) + getdeg(Y, m) > 2) 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 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 7 ms 20316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 289 ms 42136 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 7 ms 20316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 7 ms 20316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 7 ms 20316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20316 KB Output is correct
2 Correct 7 ms 20368 KB Output is correct
3 Incorrect 7 ms 20316 KB Output isn't correct
4 Halted 0 ms 0 KB -