oj.uz

Submission #617991

# Submission time Handle Problem Language Result Execution time Memory
617991 2022-08-01T18:48:10 Z GlassesNerd Swapping Cities (APIO20_swap) C++17
6 / 100
 599 ms 64112 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<climits>
#include"swap.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n, m;
vector<pair<ll, pair<ll, ll>>> edges;
vector<vector<ll>> binlift;
vector<ll> depths;
vector<ll> swapp;

ll getp(ll x, vector<ll>& dsu) {
	if (dsu[x] == x)return x;
	return dsu[x] = getp(dsu[x], dsu);
}
void merge(ll a, ll b, ll x, vector<ll>& dsu) {
	a = getp(a, dsu);
	b = getp(b, dsu);
	dsu[a] = x;
	dsu[b] = x;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	for (ll i = 0; i < m; i++) {
		edges.push_back({ W[i], {U[i], V[i]} });
	}
	sort(edges.begin(), edges.end());
	vector<ll> dsu(n + m);
	for (ll i = 0; i < n + m; i++)dsu[i] = i;
	swapp.assign(n + m, LLONG_MAX / 2);
	vector<vector<ll>>child(n + m);
	vector<ll>deg(n, 0);
	binlift.assign(n + m, vector<ll>(20, -1));
	for (ll i = 0; i < m; i++) {
		ll a = edges[i].ss.ff;
		ll b = edges[i].ss.ss;
		ll oa = a;
		ll ob = b;
		a = getp(a, dsu);
		b = getp(b, dsu);
		if (a != b) {
			merge(a, b, i + n, dsu);
			binlift[a][0] = i + n;
			binlift[b][0] = i + n;
			if (swapp[a] != LLONG_MAX / 2 || swapp[b] != LLONG_MAX / 2 || (deg[oa] >= 2 && deg[ob] >= 2)) {
				swapp[i + n] = edges[i].ff;
			}
			child[i + n].push_back(a);
			child[i + n].push_back(b);
		}
		else {
			swapp[a] = min(swapp[a], edges[i].ff);
		}
		deg[oa]++;
		deg[ob]++;
	}
	depths.assign(n + m, 0);
	for (ll i = n + m - 1; i >= 0; i--) {
		for (ll j = 0; j < child[i].size(); j++) {
			depths[child[i][j]] = depths[i] + 1;
			swapp[child[i][j]] = min(swapp[child[i][j]], swapp[i]);
		}
	}
	for (ll i = n + m - 1; i >= 0; i--) {
		ll j = 0;
		while (binlift[i][j] != -1) {
			binlift[i][j + 1] = binlift[binlift[i][j]][j];
			j++;
		}
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	if (depths[X] < depths[Y]) {
		ll tmp = X;
		X = Y;
		Y = tmp;
	}
	while (depths[X] != depths[Y]) {
		X = binlift[X][floor(log2(depths[X] - depths[Y]))];
	}
	while (X != Y) {
		ll i = 19;
		while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
		X = binlift[X][i];
		Y = binlift[Y][i];
	}
	return swapp[X] == LLONG_MAX / 2 ? -1 : swapp[Y];
}
/*signed main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> U(M), V(M), W(M);
	for (ll i = 0; i < M; i++)cin >> U[i] >> V[i] >> W[i];
	init(N, M, U, V, W);
	ll Q;
	cin >> Q;
	while (Q--) {
		ll a, b;
		cin >> a >> b;
		cout << getMinimumFuelCapacity(a, b) << "\n";
	}
}*/

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:65:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (ll j = 0; j < child[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 98 ms 46772 KB Output is correct
10 Correct 131 ms 57196 KB Output is correct
11 Correct 128 ms 56168 KB Output is correct
12 Correct 143 ms 59512 KB Output is correct
13 Correct 198 ms 60228 KB Output is correct
14 Correct 120 ms 47036 KB Output is correct
15 Correct 330 ms 61500 KB Output is correct
16 Correct 281 ms 59820 KB Output is correct
17 Correct 314 ms 63384 KB Output is correct
18 Correct 599 ms 64112 KB Output is correct
19 Correct 91 ms 13276 KB Output is correct
20 Correct 297 ms 61500 KB Output is correct
21 Correct 279 ms 59256 KB Output is correct
22 Correct 309 ms 63428 KB Output is correct
23 Correct 578 ms 64068 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Incorrect 1 ms 852 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 98 ms 46772 KB Output is correct
11 Correct 131 ms 57196 KB Output is correct
12 Correct 128 ms 56168 KB Output is correct
13 Correct 143 ms 59512 KB Output is correct
14 Correct 198 ms 60228 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Incorrect 1 ms 852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 98 ms 46772 KB Output is correct
10 Correct 131 ms 57196 KB Output is correct
11 Correct 128 ms 56168 KB Output is correct
12 Correct 143 ms 59512 KB Output is correct
13 Correct 198 ms 60228 KB Output is correct
14 Correct 120 ms 47036 KB Output is correct
15 Correct 330 ms 61500 KB Output is correct
16 Correct 281 ms 59820 KB Output is correct
17 Correct 314 ms 63384 KB Output is correct
18 Correct 599 ms 64112 KB Output is correct
19 Incorrect 520 ms 59704 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 98 ms 46772 KB Output is correct
11 Correct 131 ms 57196 KB Output is correct
12 Correct 128 ms 56168 KB Output is correct
13 Correct 143 ms 59512 KB Output is correct
14 Correct 198 ms 60228 KB Output is correct
15 Correct 120 ms 47036 KB Output is correct
16 Correct 330 ms 61500 KB Output is correct
17 Correct 281 ms 59820 KB Output is correct
18 Correct 314 ms 63384 KB Output is correct
19 Correct 599 ms 64112 KB Output is correct
20 Incorrect 520 ms 59704 KB Output isn't correct
21 Halted 0 ms 0 KB -