oj.uz

답안 #149803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149803 2019-09-01T07:11:42 Z 채원♡예나(#3706, rhrnald, ohjw420, chris2tg) 로카히아 유적 (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<pii> Q;

vector<pii> 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 i=0; !q.empty(); i++) {
		nq.clear();
		for(int i=0; i<(int)q.size(); i+=2) {
			if(i==(int)q.size()-1) {
				lft.push_back({q[i], i});
			}
			if(merge(q[i], q[i+1])) {
				nq.push_back(q[i]);
			} else {
				Q.push_back({q[i], q[i+1]});
			}
		}
		q=nq;
	}

	if(lft.empty()) return -1;

	int X=lft.back().first;
	for(int i=0; i<(int)lft.size()-1; i++) merge(X, lft[i].first);
	for(int i=0; i<(int)Q.size(); i++) merge(X, Q[i].first), merge(X, Q[i].second);

	if(sz[X]>(n/2)) return h[X];
	else return -1;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 262144 KB Time limit exceeded
2 Execution timed out 3055 ms 262144 KB Time limit exceeded
3 Correct 6 ms 640 KB Correct : C = 226
4 Execution timed out 3050 ms 262144 KB Time limit exceeded
5 Correct 7 ms 640 KB Correct : C = 247
6 Execution timed out 3040 ms 262144 KB Time limit exceeded
7 Runtime error 1269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 3053 ms 262144 KB Time limit exceeded
9 Execution timed out 3032 ms 262144 KB Time limit exceeded
10 Correct 6 ms 640 KB Correct : C = 100
11 Execution timed out 3030 ms 262144 KB Time limit exceeded
12 Execution timed out 3031 ms 262144 KB Time limit exceeded
13 Correct 6 ms 640 KB Correct : C = 117
14 Execution timed out 3047 ms 262144 KB Time limit exceeded
15 Correct 5 ms 512 KB Correct : C = 179
16 Correct 6 ms 640 KB Correct : C = 299
17 Correct 6 ms 640 KB Correct : C = 286
18 Execution timed out 3049 ms 262144 KB Time limit exceeded
19 Execution timed out 3045 ms 262144 KB Time limit exceeded
20 Execution timed out 3059 ms 262144 KB Time limit exceeded
21 Correct 6 ms 512 KB Correct : C = 144
22 Execution timed out 3063 ms 262144 KB Time limit exceeded
23 Correct 5 ms 512 KB Correct : C = 60
24 Correct 6 ms 640 KB Correct : C = 105
25 Execution timed out 3033 ms 262144 KB Time limit exceeded
26 Execution timed out 3043 ms 262144 KB Time limit exceeded
27 Runtime error 973 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)