Submission #1191683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191683		lovrot	Swapping Cities (APIO20_swap)	C++20	37 / 100	2094 ms	15008 KiB

swap

#include "swap.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int OO = 1e9 + 10;

vector<pii> g[N];

void init(int n, int m,
          vector<int> U, vector<int> V, vector<int> W) {
	for(int i = 0; i < m; ++i) { 
		g[U[i]].PB({V[i], W[i]});
		g[V[i]].PB({U[i], W[i]});
	}
}

int bio[N], sum, siz, tri;

void dfs(int u, int k) { 
	if(bio[u]) return;
	bio[u] = 1;
	siz ++;

	int cnt = 0;
	for(pii e : g[u]) { 
		if(e.Y <= k) {
			dfs(e.X, k);
			sum ++;
			cnt ++;
		}
	}
	tri = max(tri, cnt);
}

int getMinimumFuelCapacity(int X, int Y) {
	int lo = -1, hi = OO;
	for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
		memset(bio, 0, sizeof(bio));
		sum = 0;
		siz = 0;
		tri = 0;

		dfs(X, mi);

		if((tri >= 3 || siz <= sum / 2) && bio[Y]) { hi = mi; }
		else { lo = mi; }
	}

	return hi == OO ? -1 : hi;
}

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