oj.uz

Submission #645196

# Submission time Handle Problem Language Result Execution time Memory
645196 2022-09-26T12:15:12 Z dooompy Swapping Cities (APIO20_swap) C++17
0 / 100
 544 ms 44516 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;
		}
	}
	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];
}

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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 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 568 KB Output is correct
9 Correct 79 ms 31404 KB Output is correct
10 Correct 105 ms 38416 KB Output is correct
11 Correct 108 ms 37736 KB Output is correct
12 Correct 111 ms 39996 KB Output is correct
13 Correct 159 ms 40612 KB Output is correct
14 Correct 102 ms 31636 KB Output is correct
15 Correct 298 ms 42660 KB Output is correct
16 Correct 253 ms 41408 KB Output is correct
17 Correct 263 ms 43784 KB Output is correct
18 Correct 544 ms 44516 KB Output is correct
19 Incorrect 90 ms 9996 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 451 ms 41180 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 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 568 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 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 568 KB Output is correct
9 Correct 79 ms 31404 KB Output is correct
10 Correct 105 ms 38416 KB Output is correct
11 Correct 108 ms 37736 KB Output is correct
12 Correct 111 ms 39996 KB Output is correct
13 Correct 159 ms 40612 KB Output is correct
14 Correct 102 ms 31636 KB Output is correct
15 Correct 298 ms 42660 KB Output is correct
16 Correct 253 ms 41408 KB Output is correct
17 Correct 263 ms 43784 KB Output is correct
18 Correct 544 ms 44516 KB Output is correct
19 Incorrect 451 ms 41180 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -