Submission #1160170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160170		usuyus	Island Hopping (JOI24_island)	C++20	100 / 100	2 ms	464 KiB

island

#include "island.h"

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

void solve(int N, int L) {

	vector<set<int>> adj(N+1);

	// {-u, v, k}; query(v, k) = u
	priority_queue<array<int, 3>> pq;

	for (int v = 1; v <= N; v++) {
		pq.push({-query(v, 1), v, 1});
	}

	while (!pq.empty()) {
		auto [u, v, k] = pq.top(); pq.pop();
		u *= -1;
		int uu;

		// u already adjacent to v
		if (adj[v].count(u)) {
			if (k+1 < N && u < v && (uu = query(v, k+1)) > u) {
				pq.push({-uu, v, k+1});
			}
			continue;
		}

		// is there a common vertex between u and v
		set<int> isect;
		set_intersection(
			adj[u].begin(), adj[u].end(), adj[v].begin(), adj[v].end(),
			inserter(isect, isect.begin())
		);

		if (isect.empty()) {
			adj[u].insert(v);
			adj[v].insert(u);
			if (k+1 < N && u < v && (uu = query(v, k+1)) > u) {
				pq.push({-uu, v, k+1});
			}
		}
	}

	for (int v = 1; v <= N; v++) {
		for (int u : adj[v]) {
			if (u < v) answer(u, v);
		}
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 9 / 9
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 22 / 22
• Subtask 8: 28 / 28