Submission #569908

#	Time	Username	Problem	Language	Result	Execution time	Memory
569908		sumit_kk10	Swapping Cities (APIO20_swap)	C++17	50 / 100	2075 ms	42240 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#include <vector>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 1e6 + 5;
vector<pair<int, int> > g[N];
vector<pair<int, pair<int, int> > > edges;
int mx, n, m, component[N], deg[N], max_deg[N], edg_cnt[N], cnt[N];
bool sb2 = 1, sb1 = 1;

int find(int x){
	while(true){
		if(x == component[x])
			return x;
		component[x] = component[component[x]];
		x = component[x];
	}
}

void merge(int a, int b){
	int u = find(a), v = find(b);
	deg[a]++;
	deg[b]++;
	max_deg[v] = max({max_deg[v], max_deg[u], deg[a], deg[b]});
	if(v != u)
		edg_cnt[v] += edg_cnt[u] + 1;
	else
		edg_cnt[v]++;
	if(u != v)
		cnt[v] += cnt[u];
	component[u] = v;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	m = M;
	int wut = 0;
	map<int, int> mp;
	for(int i = 0; i < M; ++i){
		int u = U[i], v = V[i], w = W[i];
		if(u != 0 and v != 0)
			sb2 = false;
		g[u].pb({w, v});
		g[v].pb({w, u});
		mx = max(mx, w);
		edges.pb({w, {u ,v}});
		mp[u]++;
		mp[v]++;
	}
	for(int i = 0; i < n; ++i)
		sort(g[i].begin(), g[i].end());
	sort(edges.begin(), edges.end());
	for(auto k : mp)
		wut = max(wut, k.S);
	if(wut > 2)
		sb1 = false;
}
 
int getMinimumFuelCapacity(int X, int Y) {
	if(sb2 and m == n - 1){
		if(n <= 3) return -1;
		if(X == 0){
			int x = g[Y][0].F, xx, dest, mn;
			if(g[0][0].S != Y){
				xx = g[0][0].F;
				dest = g[0][0].S;
			}else{
				xx = g[0][1].F;
				dest = g[0][1].S;
			}
			if(g[0][1].S != Y and g[0][1].S != dest)
				mn = g[0][1].F;
			else
				mn = g[0][2].F;
			return max({x, xx, mn});
		}
		int x = g[X][0].F, xx = g[Y][0].F, mn;
		if(g[0][0].S != X and g[0][0].S != Y)
			mn = g[0][0].F;
		else if(g[0][1].S != X and g[0][1].S != Y)
			mn = g[0][1].F;
		else
			mn = g[0][2].F;
		return max({x, xx, mn});
	}
	if(sb1){
		if(m == n - 1)
			return -1;
		else
			return mx;
	}
	for(int i = 0; i < n; ++i){
		component[i] = i;
		deg[i] = 0;
		max_deg[i] = 0;
		edg_cnt[i] = 0;
		cnt[i] = 1;
	}
	for(auto k : edges){
		int u = k.S.F, v = k.S.S, c = k.F;
		merge(u, v);
		// cout << ((max_deg[find(X)] > 2) or (edg_cnt[find(X)] >= cnt[find(X)])) << endl;
		if(find(X) == find(Y) and ((max_deg[find(X)] > 2) or (edg_cnt[find(X)] >= cnt[find(X)])))
			return c;
	}
	return -1;
}

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