Submission #1069411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069411		pawned	Swapping Cities (APIO20_swap)	C++17	37 / 100	2072 ms	25172 KiB

swap

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "swap.h"

const int MAX = 1e5 + 5;

int N, M;

vector<ii> adj[MAX];	// {vertex, dist}

vi wt;

void init(int N_g, int M_g, vi U_g, vi V_g, vi W_g) {
	N = N_g;
	M = M_g;
	for (int i = 0; i < M; i++) {
		adj[U_g[i]].pb({V_g[i], W_g[i]});
		adj[V_g[i]].pb({U_g[i], W_g[i]});
		wt.pb(W_g[i]);
	}
	sort(wt.begin(), wt.end());
}

bool check(int cut, int X, int Y) {
	vi adjc[N];
	for (int i = 0; i < N; i++) {
		for (ii p : adj[i]) {
			if (p.se <= cut)
				adjc[i].pb(p.fi);
		}
	}
	vector<bool> vis(N, false);
	queue<int> q;
	q.push(X);
	vis[X] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adjc[x]) {
			if (!vis[y]) {
				q.push(y);
				vis[y] = true;
			}
		}
	}
	if (!vis[Y])
		return false;
	vi adjd[N];
	for (int i = 0; i < N; i++) {
		if (!vis[i])
			continue;
		for (int x : adjc[i]) {
			if (vis[x])
				adjd[i].pb(x);
		}
	}
	int cnte = 0;	// number of edges
	int sz = 0;	// number of vertices
	for (int i = 0; i < N; i++) {
		cnte += adjd[i].size();
		if (adjd[i].size() >= 1)
			sz++;
	}
	cnte /= 2;
//	cout<<"sz, cnte: "<<sz<<" "<<cnte<<endl;
	if (cnte > sz - 1)	// has a cycle
		return true;
	for (int i = 0; i < N; i++) {
		if (adjd[i].size() >= 3)
			return true;
	}
	return false;
}

int getMinimumFuelCapacity(int X, int Y) {
//	cout<<check(3, X, Y)<<endl;
	int low = 0;
	int high = M - 1;
	int ans = -1;	// minimum so can pass
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		if (check(wt[mid], X, Y)) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	if (ans != -1)
		return wt[ans];
	return -1;
}

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