oj.uz

Submission #151699

# Submission time Handle Problem Language Result Execution time Memory
151699 2019-09-04T08:10:52 Z gs14004 Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 3 ms 716 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Correct : C = 205
2 Correct 2 ms 504 KB Correct : C = 118
3 Correct 3 ms 504 KB Correct : C = 202
4 Correct 2 ms 504 KB Correct : C = 120
5 Correct 2 ms 504 KB Correct : C = 4
6 Correct 2 ms 632 KB Correct : C = 177
7 Correct 2 ms 504 KB Correct : C = 118
8 Correct 3 ms 504 KB Correct : C = 198
9 Correct 2 ms 632 KB Correct : C = 117
10 Correct 2 ms 504 KB Correct : C = 194
11 Correct 3 ms 632 KB Correct : C = 197
12 Correct 3 ms 504 KB Correct : C = 198
13 Correct 3 ms 504 KB Correct : C = 277
14 Correct 3 ms 632 KB Correct : C = 263
15 Correct 2 ms 504 KB Correct : C = 0
16 Correct 2 ms 504 KB Correct : C = 177
17 Correct 2 ms 632 KB Correct : C = 178
18 Correct 3 ms 632 KB Correct : C = 203
19 Correct 3 ms 504 KB Correct : C = 273
20 Correct 3 ms 504 KB Correct : C = 251
21 Correct 3 ms 560 KB Correct : C = 199
22 Correct 2 ms 632 KB Correct : C = 117
23 Correct 3 ms 632 KB Correct : C = 298
24 Correct 3 ms 716 KB Correct : C = 297
25 Correct 2 ms 508 KB Correct : C = 119
26 Correct 2 ms 632 KB Correct : C = 163
27 Correct 2 ms 632 KB Correct : C = 197