제출 #1160342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160342		WH8	Island Hopping (JOI24_island)	C++20	65 / 100	3 ms	788 KiB

island

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

int ans[305][305];


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=ans[i][ck]=(ans[i][ck]==0?query(i, ck):ans[i][ck]);
			if(par(res)==par(i))break;
			int cor;
			if(ck==a[i]+1)cor=i;
			else{
				cor=ans[res][a[res]+1]=(ans[res][a[res]+1]==0?query(res, a[res]+1):ans[res][a[res]+1]);
			}
			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: 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