oj.uz

Submission #379428

# Submission time Handle Problem Language Result Execution time Memory
379428 2021-03-18T08:30:16 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),rng2(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,300){
		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);
		}
	}
	REP(i,300){
		int a=rng2()%n,b=rng2()%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 1 ms 620 KB Partially correct : C = 366
2 Partially correct 1 ms 620 KB Partially correct : C = 600
3 Partially correct 1 ms 620 KB Partially correct : C = 600
4 Incorrect 1 ms 620 KB Wrong
5 Partially correct 1 ms 620 KB Partially correct : C = 341
6 Correct 1 ms 620 KB Correct : C = 66
7 Correct 1 ms 620 KB Correct : C = 39
8 Partially correct 2 ms 620 KB Partially correct : C = 600
9 Partially correct 2 ms 620 KB Partially correct : C = 600
10 Partially correct 1 ms 620 KB Partially correct : C = 600
11 Partially correct 2 ms 620 KB Partially correct : C = 600
12 Partially correct 1 ms 620 KB Partially correct : C = 600
13 Correct 1 ms 620 KB Correct : C = 62
14 Execution timed out 1078 ms 492 KB Time limit exceeded
15 Correct 1 ms 492 KB Correct : C = 1
16 Correct 1 ms 620 KB Correct : C = 39
17 Incorrect 1 ms 620 KB Wrong
18 Partially correct 1 ms 620 KB Partially correct : C = 600
19 Correct 1 ms 620 KB Correct : C = 295
20 Partially correct 1 ms 620 KB Partially correct : C = 468
21 Partially correct 1 ms 620 KB Partially correct : C = 600
22 Partially correct 2 ms 620 KB Partially correct : C = 600
23 Partially correct 1 ms 620 KB Partially correct : C = 331
24 Correct 1 ms 620 KB Correct : C = 162
25 Incorrect 1 ms 620 KB Wrong
26 Incorrect 1 ms 620 KB Wrong
27 Partially correct 1 ms 620 KB Partially correct : C = 600