Submission #379429

#	Time	Username	Problem	Language	Result	Execution time	Memory
379429		zaneyu	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	1098 ms	640 KiB

lokahia

#include "lokahia.h"
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define sz(x) (int)x.size()
#define MXTO(x,y) x=max(x,y)
#define MNTO(x,y) x=min(x,y)
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
const int maxn=200+5;
const int MOD=1e9+7;
int par[maxn];
int rank1[maxn];
inline int find(int a){
	if(par[a]==a) return a;
	return par[a]=find(par[a]);
}
inline void merge(int a,int b){
	a=find(a),b=find(b);
	if(a==b) return;
	rank1[a]+=rank1[b];
	par[b]=a;
}
mt19937 rng(420);
map<pii,int> mp;
int query(int a,int b){
	if(a>b) swap(a,b);
	if(mp.count({a,b})) return mp[{a,b}];
	return mp[{a,b}]=CollectRelics(a,b);
}
int FindBase(int n){
	REP(i,n) par[i]=i,rank1[i]=1;
	//REP(i,n) REP(j,i) cout<<i<<' '<<j<<' '<<CollectRelics(i,j)<<'\n';
	
	REP(i,600){
		int a=rng()%n,b=rng()%n;
		if(find(a)==find(b)){
			i--;
			continue;
		}
		a=find(a),b=find(b);
		int z=query(a,b);
		if(z==-1) continue;
		//cout<<a<<' '<<b<<' '<<z<<'\n';
		merge(z,a);
		merge(z,b);
		if(rank1[find(z)]>n/2){
			return find(z);
		}
	}
	return -1;
}

• Subtask 1: 0 / 100