Submission #1160338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160338		WH8	Island Hopping (JOI24_island)	C++20	2 / 100	2 ms	420 KiB

island

#include <bits/stdc++.h>
using namespace std;
#include "island.h"
#define f first
#define s second

int p[305];
int par(int x){
	if(p[x]==0)return x;
	return p[x]=par(p[x]);
}
bool merge(int a,int b){
	int x=par(a),y=par(b);
	if(x==y)return 0;
	p[x]=y;
	return 1;
}

void solve(int n, int L) {
	int a[n+1];fill(a,a+n+1,0);
	set<pair<int,int>> s;
	for(int i=1;i<=n;i++){
		// start asking whether a[i]+1
		for(int ck=a[i]+1;ck<n-1;ck++){
			int res=query(i, ck);
			if(par(res)==par(i))break;
			int cor;
			if(ck==a[i]+1)cor=i;
			else{
				cor=query(res, a[res]+1);
				if(a[res]==0){
					merge(cor, res);
					s.insert({min(cor, res), max(cor,res)});
				}
			}
			if(cor==i){
				a[res]++;	
				if(merge(i, res)) s.insert({i, res});
			}
			else break;
		}
	}

	//~ assert(s.size()==n-1);
	for(auto it:s){
		//~ cout<<it.f<<" "<<it.s<<endl;
		answer(it.f,it.s);
	}
}

• 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