Submission #1306048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306048		vlomaczk	Island Hopping (JOI24_island)	C++20	65 / 100	5 ms	460 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 310;
vector<int> rep(M);
int ile;

int Find(int v) {
	return (rep[v] == v ? v : rep[v] = Find(rep[v]));
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if(a==b) return;
	ile--;
	rep[a] = b;
}

void solve(int N, int L) {
	ile = N;
	for(int i=1; i<=N; ++i) rep[i] = i;
	vector<int> next(N+1, 1);
	set<pair<int, int>> bridges;
	vector<pair<int, int>> ans;
	vector<int> curr;
	for(int i=1; i<=N; ++i) curr.push_back(i);
	while(ile > 1 && curr.size()) {
		vector<int> new_cr;
		for(auto x : curr) {
			if(next[x] < N) {
				int odp = query(x, next[x]);
				next[x]++;
				if(bridges.find({x, odp})!=bridges.end()) continue;
				if(bridges.find({odp, x})!=bridges.end() && Find(x) != Find(odp)) {
					ans.push_back({x,odp});
					Union(x, odp);
					new_cr.push_back(x);
					new_cr.push_back(odp);
				}
				bridges.insert({x,odp});
			}
		}
		swap(curr, new_cr);
	}
	for(auto[a,b] : ans) answer(a,b);
}

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