Submission #678622

#	Time	Username	Problem	Language	Result	Execution time	Memory
678622		Dan4Life	Swapping Cities (APIO20_swap)	C++17	37 / 100	2054 ms	17424 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define SZ(a) (int)a.size()
using ll = long long;

const int maxn = (int)1e5+10;
const int INF = (ll)1e9;

vector<pair<int,int>> adj[maxn];
ll dis[maxn]; int tot = 0;
int par[maxn];
bool vis[maxn];
int n, m, p[maxn], sz[maxn];

int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }

bool unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return false;
	if(sz[x] < sz[y]) swap(x,y);
	p[y]=x, sz[x]+=sz[y];
	return true;
}

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++){
		adj[u[i]].pb({v[i],w[i]});
		adj[v[i]].pb({u[i],w[i]});
	}
}

bool chk(int w, int x, int y){
	int mx_deg = 0, cnt = 0;
	for(int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
	for(int i = 0; i < n; i++)
		for(auto u : adj[i])
			if(u.se<=w) unionSet(i,u.fi);
	if(!isSameSet(x,y)) return 0;
	bool ok = true;
	for(int i = 0; i < n; i++){
		if(!isSameSet(i,x)) continue;
		int deg = 0;
		for(auto u : adj[i])
			if(u.se<=w) deg++;
		if(mx_deg<deg) mx_deg=deg,cnt=1;
		else if(mx_deg==deg) cnt++;
		if(deg==1) ok=0;
	}
	if(mx_deg>=3) return 1;
	if(mx_deg<=1) return 0;
	return ok;
}

/*
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
*/
int getMinimumFuelCapacity(int x, int y) {
	int l = 1, r = INF+1;
	while(l<r){
		int mid = (l+r)/2;
		if(chk(mid,x,y)) r=mid;
		else l=mid+1;
	}
	return (l==INF+1?-1:l);
}

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