oj.uz

Submission #379429

# Submission time Handle Problem Language Result Execution time Memory
379429 2021-03-18T08:34:33 Z zaneyu Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 640 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(420);
map<pii,int> mp;
int query(int a,int b){
	if(a>b) swap(a,b);
	if(mp.count({a,b})) return mp[{a,b}];
	return mp[{a,b}]=CollectRelics(a,b);
}
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=query(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 = 403
2 Correct 1 ms 620 KB Correct : C = 171
3 Execution timed out 1098 ms 492 KB Time limit exceeded
4 Correct 1 ms 620 KB Correct : C = 67
5 Correct 1 ms 620 KB Correct : C = 59
6 Incorrect 1 ms 640 KB Wrong
7 Incorrect 2 ms 620 KB Wrong
8 Correct 1 ms 620 KB Correct : C = 257
9 Partially correct 1 ms 620 KB Partially correct : C = 593
10 Partially correct 1 ms 620 KB Partially correct : C = 570
11 Correct 1 ms 620 KB Correct : C = 225
12 Correct 2 ms 620 KB Correct : C = 237
13 Incorrect 2 ms 620 KB Wrong
14 Correct 1 ms 620 KB Correct : C = 267
15 Partially correct 1 ms 620 KB Partially correct : C = 590
16 Correct 1 ms 620 KB Correct : C = 35
17 Partially correct 1 ms 620 KB Partially correct : C = 317
18 Partially correct 1 ms 620 KB Partially correct : C = 310
19 Correct 1 ms 620 KB Correct : C = 164
20 Correct 1 ms 620 KB Correct : C = 38
21 Incorrect 1 ms 620 KB Wrong
22 Incorrect 2 ms 620 KB Wrong
23 Partially correct 2 ms 620 KB Partially correct : C = 477
24 Partially correct 2 ms 620 KB Partially correct : C = 395
25 Correct 1 ms 492 KB Correct : C = 1
26 Partially correct 1 ms 620 KB Partially correct : C = 560
27 Partially correct 2 ms 620 KB Partially correct : C = 498