oj.uz

Submission #401051

# Submission time Handle Problem Language Result Execution time Memory
401051 2021-05-09T09:22:39 Z saleh Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 27220 KB 
#include "swap.h"

#include <bits/stdc++.h>

#define sd second
#define ft first

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23, MAXM = 200 * 1000 + 23;















int n, m, a[MAXM];

int par[MAXN], ot[MAXN], deg[MAXN], comp[MAXN];
vector<pii> cn[MAXN];
vector<int> r[MAXN];

int get(int x) { return (par[x] >= 0? par[x] = get(par[x]): x); }
bool mrg(int x, int y, int w) {
	int u = get(x), v = get(y);
	if (u == v) return true;
	deg[x]++, deg[y]++;
	if (par[u] < par[v]) swap(u, v);
	for (auto i : r[u]) {
		r[v].push_back(i);
		comp[i] = comp[v];
		cn[i].push_back({comp[v], w});
	}
	par[v] += par[u];
	par[u] = v;
	if (deg[x] > 2 || deg[y] > 2) return true;
	return ((ot[comp[u]] != -1) || (ot[comp[v]] != -1));
}


void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	memset(ot, -1, sizeof ot);
	memset(par, -1, sizeof par);
	iota(comp, comp + n, 0);
	for (int i = 0; i < n; i++) {
		cn[i].push_back({i, -1});
		r[i].push_back(i);
	}
	iota(a, a + m, 0);
	sort(a, a + m, [W](int x, int y) { return W[x] < W[y]; });
	for (int o = 0; o < m; o++) {
		int i = a[o];
		if (mrg(U[i], V[i], W[i])) if (ot[comp[U[i]]] == -1) ot[comp[U[i]]] = W[i]; 
	}
}

int getMinimumFuelCapacity(int x, int y) {
	if (x == y) return 0;//
	int jav = -1, jabe = -1;
	for (auto i : cn[x]) {
		int ans = -1;
		for (auto j : cn[y]) if (i.ft == j.ft) {
			ans = max(i.sd, j.sd);
			break;
		}
		if (~ans) if (jav == -1 || jav > ans) {
			jav = ans;
			jabe = i.ft; 
		}
	}
	int ind = 0;
	while (cn[x][ind].ft != jabe) ind++;
	while (ind < cn[x].size() && ot[cn[x][ind].ft] == -1) ind++;
	if (ind == cn[x].size()) return -1;
	return max(jav, ot[cn[x][ind].ft]);
}
/*
int main() {
	init(5, 6, {0,0,1,1,1,2}, {1,2,2,3,4,3}, {4,4,1,2,10,3});
	cout << getMinimumFuelCapacity(1, 2) << endl << getMinimumFuelCapacity(2, 4) << endl << getMinimumFuelCapacity(0, 1) << endl;
	return 0;
}*/

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (ind < cn[x].size() && ot[cn[x][ind].ft] == -1) ind++;
      |         ~~~~^~~~~~~~~~~~~~
swap.cpp:87:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  if (ind == cn[x].size()) return -1;
      |      ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 5 ms 5772 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Execution timed out 2081 ms 22252 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Execution timed out 2061 ms 27220 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 5 ms 5772 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 4 ms 5708 KB Output is correct
10 Correct 5 ms 5916 KB Output is correct
11 Incorrect 5 ms 5964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 5 ms 5772 KB Output is correct
5 Correct 4 ms 5836 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 5 ms 5836 KB Output is correct
10 Execution timed out 2081 ms 22252 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 5 ms 5772 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Execution timed out 2081 ms 22252 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 5 ms 5772 KB Output is correct
5 Correct 4 ms 5836 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 5 ms 5836 KB Output is correct
10 Execution timed out 2081 ms 22252 KB Time limit exceeded
11 Halted 0 ms 0 KB -