제출 #1158816

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

island

#include "island.h"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

//query
//answer

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

void solve(int n, int l){
	int ptr[n+5];
	memset(ptr,0,sizeof(ptr));
	
	set<int>se[n+5];
	
	int val[n+5];
	for(int x=1;x<=n;x++){
		ptr[x]=1;
		val[x]=query(x,ptr[x]);
	}
	
	DSU dsu;
	dsu.init(n+5);
	
	for(int x=0;x<n-1;x++){
		for(int y=1;y<=n;y++){
			if(val[y]==-1) continue;
			if(val[val[y]]==-1) continue;
			if(y==val[val[y]]){
				int nxt=val[y];
				answer(y,nxt);
				dsu.unite(y,nxt);
				se[y].insert(nxt);
				se[nxt].insert(y);
				ptr[y]++;
				ptr[nxt]++;
				if(ptr[nxt]==n) val[nxt]=-1;
				else{
					while(1){
						val[nxt]=query(nxt,ptr[nxt]);
						if(se[nxt].find(val[nxt])==se[nxt].end()) break;
						ptr[nxt]++;
						if(ptr[nxt]==n){
							val[nxt]=-1;
							break;
						}
					}
				}
				if(ptr[y]==n) val[y]=-1;
				else{
					while(1){
						val[y]=query(y,ptr[y]);
						if(se[y].find(val[y])==se[y].end()) break;
						ptr[y]++;
						if(ptr[y]==n){
							val[y]=-1;
							break;
						}
					}
				}
				break;
			}
		}
		
		//check
		for(int y=1;y<=n;y++){
			if(val[y]==-1) continue;
			if(dsu.get(y)==dsu.get(val[y])){
				val[y]=-1;
			}
		}
	}
}

• 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