Submission #151699

#	Time	Username	Problem	Language	Result	Execution time	Memory
151699		gs14004	Lokahian Relics (FXCUP4_lokahia)	C++17	100 / 100	3 ms	716 KiB

lokahia

#include "lokahia.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using group = pair<vector<int>, vector<int>>;

int lca(int x, int y){
	return x == y ? x : CollectRelics(x, y);
}

int FindBase(int N){
	vector<group> grp;
	group g;
	for(int i=0; i<N; i++){
		if(sz(g.first) == 0){
			g.first.push_back(i);
			continue;
		}
		int query = lca(g.first[0], i);
		if(query == -1){
			g.second.push_back(i);
		}
		else{
			g.first.push_back(i);
			g.first[0] = query;
		}
		if(sz(g.first) == sz(g.second)){
			grp.push_back(g);
			group h; g = h;
		}
	}
	if(sz(g.first)) grp.push_back(g);
	int who = grp.back().first[0];
	int cnt = 0;
	for(auto &i : grp){
		int comp = lca(i.first[0], who);
		if(comp != -1){
			who = comp;
			cnt += sz(i.first);
		}
		else{
			for(auto &j : i.second){
				int L = lca(who, j);
				if(L != -1) who = L, cnt++;
			}
		}
	}
	if(cnt >= N / 2 + 1) return who;
	return -1;
}

• Subtask 1: 100 / 100