oj.uz

Submission #568809

# Submission time Handle Problem Language Result Execution time Memory
568809 2022-05-26T08:25:23 Z _karan_gandhi Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 11800 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

struct DSU { // Sorry UFDS
	vector<int> p, s, degree;
	vector<bool> swappable;
	int components;

	void init(int n) {
		p = vector<int>(n);
		iota(all(p), 0);
		s = vector<int>(n, 1);
		swappable = vector<bool>(n, 0);
		degree = vector<int>(n, 0);
		components = n;
	}

	int get(int x) {
		return p[x] = (p[x] == x ? x : get(p[x]));
	}

	void unite(int a, int b) {
		degree[a]++;
		degree[b]++;
		bool _swappable = 0;
		if (degree[a] >= 3 || degree[b] >= 3) _swappable = 1;

		a = get(a);
		b = get(b);

		if (a == b) {
			swappable[a] = 1;
			return;
		}

		if (s[a] > s[b]) swap(a, b);


		p[a] = b;
		s[b] += s[a];
		swappable[a] = (swappable[a] | swappable[b] | _swappable);
		components--;
	}

	bool same_set(int a, int b) {
		return get(a) == get(b);
	}

	int size(int x) {
		return s[get(x)];
	}

	bool is_swappable(int a, int b) {
		return same_set(a, b) && swappable[get(a)] && swappable[get(b)];
	}
};

int n, m;
vector<vector<pair<int, int>>> adj;
vector<pair<int, pair<int, int>>> edges;
int inf = 1e9 + 7;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	adj.resize(n);

	for (int i = 0; i < m; i++) {
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
		edges.emplace_back(W[i], make_pair(U[i], V[i]));
	}

	sort(all(edges));
}

int getMinimumFuelCapacity(int x, int y) {
	int ptr = 0;
	DSU dsu;
	dsu.init(n);
	// cout << pl(x) << pl(y) << endl;
	while (!dsu.is_swappable(x, y) && ptr < m) {
		// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;
		// cout << pl(edges[ptr]) << endl;
		dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
		ptr++;
	}
	// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;

	if (!dsu.is_swappable(x, y)) return -1;
	// if (ptr == m && !dsu.swappable[dsu) return -1;

	return edges[ptr - 1].first;
}

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 1 ms 212 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 58 ms 7804 KB Output is correct
10 Correct 84 ms 9036 KB Output is correct
11 Correct 86 ms 8896 KB Output is correct
12 Correct 85 ms 9284 KB Output is correct
13 Correct 81 ms 9312 KB Output is correct
14 Execution timed out 2055 ms 7948 KB Time limit exceeded
15 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 Execution timed out 2073 ms 11800 KB Time limit exceeded
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 1 ms 212 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.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 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 58 ms 7804 KB Output is correct
11 Correct 84 ms 9036 KB Output is correct
12 Correct 86 ms 8896 KB Output is correct
13 Correct 85 ms 9284 KB Output is correct
14 Correct 81 ms 9312 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 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 1 ms 212 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 58 ms 7804 KB Output is correct
10 Correct 84 ms 9036 KB Output is correct
11 Correct 86 ms 8896 KB Output is correct
12 Correct 85 ms 9284 KB Output is correct
13 Correct 81 ms 9312 KB Output is correct
14 Execution timed out 2055 ms 7948 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 58 ms 7804 KB Output is correct
11 Correct 84 ms 9036 KB Output is correct
12 Correct 86 ms 8896 KB Output is correct
13 Correct 85 ms 9284 KB Output is correct
14 Correct 81 ms 9312 KB Output is correct
15 Execution timed out 2055 ms 7948 KB Time limit exceeded
16 Halted 0 ms 0 KB -