oj.uz

Submission #150088

# Submission time Handle Problem Language Result Execution time Memory
150088 2019-09-01T07:41:53 Z 채원♡예나(#3706, rhrnald, ohjw420, chris2tg) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 7 ms 640 KB 
#include "lokahia.h"
#include <vector>
#include <queue>
using namespace std;

int h[300];
int sz[300];
typedef pair<int,int> pii;
vector<int> q,nq;
vector<int> Q;

vector<int> lft;
bool merge(int x, int y) {
	int t;
	if(h[x]==h[y]) t=h[x];
	else t=CollectRelics(h[x],h[y]);
	if(t<0) return false;
	h[x]=t;
	sz[x]+=sz[y];
	return true;
}
int FindBase(int N){ int n=N;
	for(int i=0; i<n; i++) q.push_back(i), h[i]=i, sz[i]=1;
	for(int j=0; j<15; j++) {
		nq.clear();
		for(int i=0; i<(int)q.size(); i+=2) {
			if(i==(int)q.size()-1) {
				lft.push_back(q[i]);
				break;
			}
			if(merge(q[i], q[i+1])) {
				nq.push_back(q[i]);
			} else {
				Q.push_back(q[i]);
				Q.push_back(q[i+1]);
			}
		}
		q=nq;
	}
	if(lft.empty()) return -1;

	int X=lft.back();
	for(int i=0; i<(int)lft.size()-1; i++) merge(X, lft[i]);
	for(int i=0; i<(int)Q.size(); i++) merge(X, Q[i]);
	if(sz[X]>(n/2)) return h[X];
	else return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Correct : C = 100
2 Correct 6 ms 640 KB Correct : C = 245
3 Correct 5 ms 512 KB Correct : C = 0
4 Correct 6 ms 640 KB Correct : C = 224
5 Correct 6 ms 512 KB Correct : C = 149
6 Correct 6 ms 640 KB Correct : C = 246
7 Correct 6 ms 640 KB Correct : C = 229
8 Correct 5 ms 640 KB Correct : C = 231
9 Correct 5 ms 512 KB Correct : C = 60
10 Correct 7 ms 640 KB Correct : C = 250
11 Correct 6 ms 640 KB Correct : C = 117
12 Correct 6 ms 512 KB Correct : C = 60
13 Correct 6 ms 512 KB Correct : C = 148
14 Correct 5 ms 512 KB Correct : C = 3
15 Correct 6 ms 512 KB Correct : C = 138
16 Correct 6 ms 640 KB Correct : C = 105
17 Correct 6 ms 640 KB Correct : C = 249
18 Correct 6 ms 512 KB Correct : C = 150
19 Correct 6 ms 512 KB Correct : C = 177
20 Correct 6 ms 640 KB Correct : C = 297
21 Correct 5 ms 512 KB Correct : C = 60
22 Correct 6 ms 640 KB Correct : C = 278
23 Correct 5 ms 512 KB Correct : C = 150
24 Correct 6 ms 512 KB Correct : C = 139
25 Correct 6 ms 640 KB Correct : C = 100
26 Correct 5 ms 640 KB Correct : C = 246
27 Correct 6 ms 512 KB Correct : C = 100