oj.uz

Submission #379427

# Submission time Handle Problem Language Result Execution time Memory
379427 2021-03-18T08:29:17 Z zaneyu Lokahian Relics (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(69);
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

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 620 KB Partially correct : C = 600
2 Partially correct 1 ms 620 KB Partially correct : C = 364
3 Correct 1 ms 620 KB Correct : C = 295
4 Partially correct 1 ms 620 KB Partially correct : C = 600
5 Partially correct 1 ms 620 KB Partially correct : C = 312
6 Correct 1 ms 620 KB Correct : C = 39
7 Partially correct 2 ms 620 KB Partially correct : C = 600
8 Incorrect 1 ms 620 KB Wrong
9 Partially correct 1 ms 620 KB Partially correct : C = 600
10 Partially correct 1 ms 620 KB Partially correct : C = 600
11 Partially correct 1 ms 620 KB Partially correct : C = 462
12 Correct 1 ms 620 KB Correct : C = 66
13 Partially correct 2 ms 620 KB Partially correct : C = 543
14 Partially correct 1 ms 620 KB Partially correct : C = 600
15 Partially correct 1 ms 620 KB Partially correct : C = 600
16 Correct 1 ms 620 KB Correct : C = 162
17 Incorrect 2 ms 620 KB Wrong
18 Correct 2 ms 620 KB Correct : C = 62
19 Correct 1 ms 620 KB Correct : C = 39
20 Partially correct 2 ms 620 KB Partially correct : C = 600
21 Partially correct 1 ms 620 KB Partially correct : C = 600
22 Incorrect 2 ms 620 KB Wrong
23 Correct 1 ms 492 KB Correct : C = 1
24 Partially correct 2 ms 620 KB Partially correct : C = 600
25 Partially correct 1 ms 620 KB Partially correct : C = 600
26 Partially correct 1 ms 620 KB Partially correct : C = 340
27 Execution timed out 1091 ms 492 KB Time limit exceeded