oj.uz

Submission #379433

# Submission time Handle Problem Language Result Execution time Memory
379433 2021-03-18T09:02:46 Z oolimry Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 640 KB 
#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << "," << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

int p[205];
int SZ[205];
int findSet(int u){
	if(u == p[u]) return u;
	else return p[u] = findSet(p[u]);
}
void unionSet(int u, int v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return;
	p[u] = v;
	SZ[v] += SZ[u];
}

mt19937 rng(time(NULL));

int FindBase(int n){
	int qrylimit = 600;
	for(int i = 0;i <= n;i++) p[i] = i, SZ[i] = 1;
	
	while(qrylimit > 0){
		int a = rng() % n, b = rng() % n;
		if(a == b) continue;
		
		if(findSet(a) == findSet(b)) continue;
		int x = CollectRelics(a,b); qrylimit--;
		
		if(x == -1) continue;
		unionSet(a,x);
		unionSet(b,x);
		
		cout << a << " " << b << " " << x << "\n";
	}
	
	for(int i = 0;i < n;i++){
		if(SZ[i] > n/2) return i;
	}
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 620 KB Wrong
2 Incorrect 1 ms 620 KB Wrong
3 Incorrect 1 ms 620 KB Wrong
4 Execution timed out 1089 ms 492 KB Time limit exceeded
5 Incorrect 1 ms 640 KB Wrong
6 Incorrect 1 ms 620 KB Wrong
7 Incorrect 2 ms 620 KB Wrong
8 Partially correct 1 ms 620 KB Partially correct : C = 600
9 Incorrect 2 ms 620 KB Wrong
10 Incorrect 1 ms 620 KB Wrong
11 Partially correct 1 ms 620 KB Partially correct : C = 600
12 Partially correct 1 ms 620 KB Partially correct : C = 600
13 Execution timed out 1083 ms 620 KB Time limit exceeded
14 Execution timed out 1090 ms 620 KB Time limit exceeded
15 Execution timed out 1067 ms 492 KB Time limit exceeded
16 Execution timed out 1097 ms 620 KB Time limit exceeded
17 Execution timed out 1082 ms 620 KB Time limit exceeded
18 Incorrect 1 ms 640 KB Wrong
19 Partially correct 1 ms 620 KB Partially correct : C = 600
20 Incorrect 2 ms 620 KB Wrong
21 Incorrect 2 ms 620 KB Wrong
22 Incorrect 2 ms 620 KB Wrong
23 Incorrect 1 ms 640 KB Wrong
24 Incorrect 1 ms 620 KB Wrong
25 Incorrect 1 ms 620 KB Wrong
26 Incorrect 2 ms 620 KB Wrong
27 Incorrect 1 ms 640 KB Wrong