oj.uz

Submission #150072

# Submission time Handle Problem Language Result Execution time Memory
150072 2019-09-01T07:40:23 Z 채원♡예나(#3706, rhrnald, ohjw420, chris2tg) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 262144 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; !q.empty(); j++) {
		nq.clear();
		for(int i=0; i<(int)q.size(); i+=2) {
			if(i==(int)q.size()-1) {
				lft.push_back(q[i]);
			}
			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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Correct : C = 226
2 Execution timed out 3114 ms 262144 KB Time limit exceeded
3 Execution timed out 3086 ms 262144 KB Time limit exceeded
4 Correct 5 ms 512 KB Correct : C = 144
5 Execution timed out 3092 ms 262144 KB Time limit exceeded
6 Correct 5 ms 512 KB Correct : C = 179
7 Correct 6 ms 640 KB Correct : C = 286
8 Correct 6 ms 640 KB Correct : C = 117
9 Execution timed out 3054 ms 262144 KB Time limit exceeded
10 Correct 6 ms 640 KB Correct : C = 100
11 Execution timed out 3031 ms 262144 KB Time limit exceeded
12 Execution timed out 3033 ms 262144 KB Time limit exceeded
13 Correct 5 ms 640 KB Correct : C = 299
14 Correct 6 ms 600 KB Correct : C = 105
15 Execution timed out 3029 ms 262144 KB Time limit exceeded
16 Execution timed out 3030 ms 262144 KB Time limit exceeded
17 Execution timed out 3091 ms 262144 KB Time limit exceeded
18 Execution timed out 3019 ms 262144 KB Time limit exceeded
19 Correct 5 ms 512 KB Correct : C = 60
20 Correct 6 ms 640 KB Correct : C = 247
21 Execution timed out 3095 ms 262144 KB Time limit exceeded
22 Execution timed out 3054 ms 262144 KB Time limit exceeded
23 Execution timed out 3112 ms 262144 KB Time limit exceeded
24 Execution timed out 3052 ms 262144 KB Time limit exceeded
25 Execution timed out 3072 ms 262144 KB Time limit exceeded
26 Execution timed out 3051 ms 262144 KB Time limit exceeded
27 Execution timed out 3068 ms 262144 KB Time limit exceeded