Submission #1069423

# Submission time Handle Problem Language Result Execution time Memory
1069423 2024-08-21T21:58:35 Z pawned Swapping Cities (APIO20_swap) C++17
0 / 100
95 ms 23628 KB
#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;


bool checkm(int cut) {	// minimum weight so has tree from 0
	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(0);
	vis[0] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adjc[x]) {
			if (!vis[y]) {
				q.push(y);
				vis[y] = true;
			}
		}
	}
	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 comp() {
	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 (checkm(wt[mid])) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return ans;
}

int minv;	// minimum so there's a tree

vi maxw(MAX, -1);

void dfs(int n) {
	for (ii p : adj[n]) {
		if (maxw[p.fi] == -1) {
			maxw[p.fi] = max(maxw[n], p.se);
			dfs(p.fi);
		}
	}
}

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());
	minv = comp();
	maxw[0] = 0;
	dfs(0);
}

int getMinimumFuelCapacity(int X, int Y) {
	if (minv == -1)
		return -1;
	return max(maxw[Y], minv);
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 2 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Incorrect 95 ms 23628 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 2 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 2 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 2 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Incorrect 2 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -