Submission #1198677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198677		Mher777	Swapping Cities (APIO20_swap)	C++17	100 / 100	155 ms	25924 KiB

swap

#include "swap.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

const int max_N = 100005;
vector<pair<int,pii>> inf[max_N];
vi g[max_N];
int sz[max_N], p[max_N], type[max_N], adj_cnt[max_N];
int n, m, timer;
vector<pair<int, pii>> edges = { {0,{0,0}} };

void make_set(int x) {
	g[x] = { x };
	p[x] = x;
	sz[x] = 1;
}

int find_set(int x) {
	if (p[x] == x) return x;
	return p[x] = find_set(p[x]);
}

void fill_information(int set_index, int new_set) {
	for (auto node : g[set_index]) {
		inf[node].pub({ timer,{ new_set,type[new_set] }});
	}
}

void union_sets(int x, int y, int w) {
	++adj_cnt[x];
	++adj_cnt[y];
	int x_set = find_set(x), y_set = find_set(y);
	if (x_set == y_set) {
		if (type[x_set]) return;
		type[x_set] = w;
		fill_information(x_set, x_set);
		return;
	}
	if (sz[x_set] < sz[y_set]) {
		swap(x_set, y_set);
	}
	sz[x_set] += sz[y_set];
	p[y_set] = x_set;
	if (!type[x_set] && (type[y_set] || adj_cnt[x] >= 3 || adj_cnt[y] >= 3)) {
		type[x_set] = w;
		fill_information(x_set, x_set);
	}
	for (auto node : g[y_set]) {
		g[x_set].pub(node);
	}
	if (!type[x_set]) return;
	type[x_set] = w;
	fill_information(y_set, x_set);
}

void init(int N, int M, vi U, vi V, vi W) {
	n = N, m = M;
	for (int i = 0; i < n; ++i) {
		make_set(i);
	}
	for (int i = 0; i < m; ++i) {
		edges.pub({ W[i],{U[i],V[i]} });
	}
	sort(all(edges));
	for (auto opt : edges) {
		if (opt.ff == 0) continue;
		++timer;
		int x = opt.ss.ff;
		int y = opt.ss.ss;
		int w = opt.ff;
		union_sets(x, y, w);
	}
}

int find_minimum(int x, int y) {
	int ret = MAX;
	for (auto opt1 : inf[x]) {
		for (auto opt2 : inf[y]) {
			int set_x = opt1.ss.ff;
			int set_y = opt2.ss.ff;
			if (set_x != set_y) continue;
			ret = min(ret, max(opt1.ss.ss,opt2.ss.ss));
		}
	}
	return ret;
	/*int l = 0, r = (int)inf[x].size() - 1, mid;
	int ret = MAX;
	while (l <= r) {
		mid = (l + r) / 2;
		int jam = inf[x][mid].ff;
		int x_set = inf[x][mid].ss;
		int ind = lower_bound(all(inf[y]), mpr(inf[x][mid].ff, -1)) - inf[y].begin() - 1;
		if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) {
			ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff));
			r = mid - 1;
			continue;
		}
		++ind;
		if (ind >= 0 && ind < (int)inf[y].size() && inf[y][ind].ss == x_set) {
			ret = min(ret, max(edges[jam].ff, edges[inf[y][mid].ff].ff));
			r = mid - 1;
			continue;
		}
		l = mid + 1;
	}
	return ret;*/
}

int getMinimumFuelCapacity(int X, int Y) {
	int x = X, y = Y;
	int ans = min(find_minimum(x, y), find_minimum(y, x));
	return (ans == MAX ? -1 : ans);
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

/*
3 2
0 1 5
0 2 5
1
1 2
*/

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27