oj.uz

Submission #618001

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

int getp(int x, vector<int>& dsu) {
	if (dsu[x] == x)return x;
	return dsu[x] = getp(dsu[x], dsu);
}
void merge(int a, int b, int x, vector<int>& 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 (int i = 0; i < m; i++) {
		edges.push_back({ W[i], {U[i], V[i]} });
	}
	sort(edges.begin(), edges.end());
	vector<int> dsu(n + m);
	for (int i = 0; i < n + m; i++)dsu[i] = i;
	swapp.assign(n + m, INT_MAX);
	vector<vector<int>>child(n + m);
	vector<int>deg(n, 0);
	binlift.assign(n + m, vector<int>(20, -1));
	for (int i = 0; i < m; i++) {
		int a = edges[i].ss.ff;
		int b = edges[i].ss.ss;
		int oa = a;
		int 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] != INT_MAX || swapp[b] != INT_MAX || (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 (int i = n + m - 1; i >= 0; i--) {
		for (int 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 (int i = n + m - 1; i >= 0; i--) {
		int 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]) {
		int tmp = X;
		X = Y;
		Y = tmp;
	}
	while (depths[X] != depths[Y]) {
		X = binlift[X][floor(log2(depths[X] - depths[Y]))];
	}
	while (X != Y) {
		int i = 19;
		while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
		X = binlift[X][i];
		Y = binlift[Y][i];
	}
	return swapp[X] == INT_MAX ? -1 : swapp[X];
}
/*signed main() {
	int N, M;
	cin >> N >> M;
	vector<int> U(M), V(M), W(M);
	for (int i = 0; i < M; i++)cin >> U[i] >> V[i] >> W[i];
	init(N, M, U, V, W);
	int Q;
	cin >> Q;
	while (Q--) {
		int 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:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int j = 0; j < child[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 86 ms 29792 KB Output is correct
10 Correct 113 ms 36360 KB Output is correct
11 Correct 113 ms 35740 KB Output is correct
12 Correct 110 ms 37840 KB Output is correct
13 Correct 161 ms 38444 KB Output is correct
14 Correct 96 ms 29836 KB Output is correct
15 Correct 250 ms 38208 KB Output is correct
16 Correct 284 ms 37156 KB Output is correct
17 Correct 268 ms 39376 KB Output is correct
18 Correct 514 ms 39992 KB Output is correct
19 Correct 100 ms 8868 KB Output is correct
20 Correct 242 ms 38348 KB Output is correct
21 Correct 275 ms 36736 KB Output is correct
22 Correct 258 ms 39380 KB Output is correct
23 Correct 514 ms 40100 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 596 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 0 ms 212 KB Output is correct
3 Correct 0 ms 372 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 86 ms 29792 KB Output is correct
11 Correct 113 ms 36360 KB Output is correct
12 Correct 113 ms 35740 KB Output is correct
13 Correct 110 ms 37840 KB Output is correct
14 Correct 161 ms 38444 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 596 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 86 ms 29792 KB Output is correct
10 Correct 113 ms 36360 KB Output is correct
11 Correct 113 ms 35740 KB Output is correct
12 Correct 110 ms 37840 KB Output is correct
13 Correct 161 ms 38444 KB Output is correct
14 Correct 96 ms 29836 KB Output is correct
15 Correct 250 ms 38208 KB Output is correct
16 Correct 284 ms 37156 KB Output is correct
17 Correct 268 ms 39376 KB Output is correct
18 Correct 514 ms 39992 KB Output is correct
19 Incorrect 503 ms 37316 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 0 ms 212 KB Output is correct
3 Correct 0 ms 372 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 86 ms 29792 KB Output is correct
11 Correct 113 ms 36360 KB Output is correct
12 Correct 113 ms 35740 KB Output is correct
13 Correct 110 ms 37840 KB Output is correct
14 Correct 161 ms 38444 KB Output is correct
15 Correct 96 ms 29836 KB Output is correct
16 Correct 250 ms 38208 KB Output is correct
17 Correct 284 ms 37156 KB Output is correct
18 Correct 268 ms 39376 KB Output is correct
19 Correct 514 ms 39992 KB Output is correct
20 Incorrect 503 ms 37316 KB Output isn't correct
21 Halted 0 ms 0 KB -