oj.uz

답안 #379426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379426 2021-03-18T08:27:53 Z zaneyu 로카히아 유적 (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 620 KB 
#include "lokahia.h"
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define sz(x) (int)x.size()
#define MXTO(x,y) x=max(x,y)
#define MNTO(x,y) x=min(x,y)
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
const int maxn=200+5;
const int MOD=1e9+7;
int par[maxn];
int rank1[maxn];
inline int find(int a){
	if(par[a]==a) return a;
	return par[a]=find(par[a]);
}
inline void merge(int a,int b){
	a=find(a),b=find(b);
	if(a==b) return;
	rank1[a]+=rank1[b];
	par[b]=a;
}
mt19937 rng(3);
int FindBase(int n){
	REP(i,n) par[i]=i,rank1[i]=1;
	//REP(i,n) REP(j,i) cout<<i<<' '<<j<<' '<<CollectRelics(i,j)<<'\n';
	
	REP(i,600){
		int a=rng()%n,b=rng()%n;
		if(find(a)==find(b)){
			i--;
			continue;
		}
		a=find(a),b=find(b);
		int z=CollectRelics(a,b);
		if(z==-1) continue;
		//cout<<a<<' '<<b<<' '<<z<<'\n';
		merge(z,a);
		merge(z,b);
		if(rank1[find(z)]>n/2){
			return find(z);
		}
	}
	return -1;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 620 KB Partially correct : C = 600
2 Correct 1 ms 492 KB Correct : C = 2
3 Partially correct 2 ms 620 KB Partially correct : C = 600
4 Partially correct 1 ms 620 KB Partially correct : C = 600
5 Partially correct 2 ms 620 KB Partially correct : C = 600
6 Execution timed out 1098 ms 492 KB Time limit exceeded
7 Correct 2 ms 620 KB Correct : C = 59
8 Incorrect 2 ms 620 KB Wrong
9 Correct 1 ms 620 KB Correct : C = 61
10 Partially correct 2 ms 620 KB Partially correct : C = 468
11 Partially correct 1 ms 620 KB Partially correct : C = 347
12 Incorrect 1 ms 620 KB Wrong
13 Correct 1 ms 620 KB Correct : C = 234
14 Correct 1 ms 620 KB Correct : C = 201
15 Partially correct 2 ms 620 KB Partially correct : C = 600
16 Partially correct 1 ms 620 KB Partially correct : C = 377
17 Partially correct 1 ms 620 KB Partially correct : C = 600
18 Partially correct 1 ms 620 KB Partially correct : C = 600
19 Partially correct 1 ms 620 KB Partially correct : C = 313
20 Correct 1 ms 620 KB Correct : C = 39
21 Correct 1 ms 620 KB Correct : C = 37
22 Incorrect 2 ms 620 KB Wrong
23 Partially correct 1 ms 620 KB Partially correct : C = 600
24 Partially correct 1 ms 620 KB Partially correct : C = 419
25 Partially correct 1 ms 620 KB Partially correct : C = 600
26 Partially correct 2 ms 620 KB Partially correct : C = 600
27 Partially correct 1 ms 620 KB Partially correct : C = 600