Submission #1257924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257924		terracottalite	Island Hopping (JOI24_island)	C++20	2 / 100	2 ms	1044 KiB

island

#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

//#define TEST

#ifndef TEST
#include "island.h"
#endif

#ifdef TEST
int query(int x, int k) {
	printf("? %d %d\n", x, k);
	fflush(stdout);
	int ret;
	scanf("%d", &ret);
	return ret;
}

void answer(int x, int y) {
	printf("! %d %d\n", x, y);
	fflush(stdout);
}
#endif

int parent[400];

int getparent(int v) {
	if (parent[v] == v) return v;
	return parent[v] = getparent(parent[v]);
}

void merge(int x, int y) {
	x = getparent(x);
	y = getparent(y);

	if (x == y) return;

	parent[y] = x;
}

void solve(int n, int l) {
	set<int> unvi;
	for (int i=1;i<=n;i++) {
		unvi.insert(i);
	}

	int d[400];
	for (int i=1;i<=n;i++) d[i] = 0;

	int s[400]; // lol
	for (int i=1;i<=n;i++) s[i] = 0;

	int mat[400][400];
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) mat[i][j] = 0;

	for (int i=1;i<=n;i++) parent[i] = i;

	set<int> st;
	
	while (!unvi.empty()) {
		int x = *unvi.begin();
		st.clear();
		while (1) {
			st.insert(x);
			int y = query(x, 1);
			int ult = y;
			d[x]++;
			if (!unvi.count(y)) {
				mat[x][y] = 1;
				mat[y][x] = 1;
				merge(x, y);
				break;
			}
			if (getparent(x) == getparent(y)) {
				int z = query(x, 2);
				d[x]++;

				if (!unvi.count(z)) {
					mat[x][z] = 1;
					mat[z][x] = 1;
					merge(x, z);
					break;
				}

				if (getparent(z) == getparent(x)) {
					s[x] = 1;
					break;
				}

				ult = z;
			}

			mat[x][ult] = 1;
			mat[ult][x] = 1;
			merge(x, ult);

			x = ult;
		}

		for (auto v : st) unvi.erase(v);
	}

	for (int i=1;i<=n;i++) {
		int x = getparent(i);
		if (s[x]) continue;
		int y = -1;
		do {
			y = query(x, ++d[x]);
		} while (getparent(y) != x);

		s[x] = 1;
	}

	/*
	int a[400][2];

	for (int i=1;i<=n;i++) {
		a[i][0] = query(i, 1);
		a[i][1] = query(i, 2);
	}



	for (int i=1;i<=n;i++) {
		mat[i][a[i][0]] = 1;
		mat[a[i][0]][i] = 1;

		if (a[i][1] != a[a[i][0]][1] && a[i][1] != a[a[i][0]][0]) {
			mat[i][a[i][1]] = 1;
			mat[a[i][1]][i] = 1;
		}
	}

	*/
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (mat[i][j] && i < j) answer(i, j);
		}
	}
}

#ifdef TEST
int main() {
	int n, l;
	scanf("%d %d", &n, &l);
	solve(n, l);
}
#endif

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