Submission #1285144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285144		Jawad_Akbar_JJ	Island Hopping (JOI24_island)	C++20	65 / 100	4 ms	888 KiB

island

#include <iostream>
#include <vector>
#include "island.h"

using namespace std;
const int M = 405;
int Dfs[M], seen2[M], Edge[M][M], cur, ec = 0, nn;

void dfs2(int u, int stp){
	for (int i=1;i<M;i++)
		if (Edge[u][i])
			seen2[i] = cur;
	if (Dfs[u])
		return;
	Dfs[u] = 1;
	for (int k=1;ec < nn - 1;k++){
		int v = query(u, k);
		if (v == stp)
			return;
		seen2[v] = cur;
		ec += 1 - Edge[u][v];
		Edge[u][v] = Edge[v][u] = 1;
	}
}

void dfs1(int u){
	cur++;
	Dfs[u] = 1;
	for (int k=1;k<u and ec < nn - 1;k++){
		int v = query(u, k);
		if (seen2[v] == cur or v > u)
			break;
		ec += 1 - Edge[u][v];
		Edge[u][v] = Edge[v][u] = 1;
		dfs2(v, u);
	}
}

void solve(int n, int l){
	nn = n;
	for (int i=n;i>=1;i--){
		if (Dfs[i] == 0){
			dfs1(i);
			continue;
		}
		for (int j=1;j<=n;j++){
			if (Edge[i][j])
				dfs2(j, i);
		}
	}

	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++)
			if (Edge[i][j])
				answer(i, j);
	}
}

• 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