oj.uz

Submission #150175

# Submission time Handle Problem Language Result Execution time Memory
150175 2019-09-01T07:50:50 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 16 ms 816 KB 
#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 205;

mt19937_64 mt(969696);

int n, dsu[N], con[N][N];
vector<int> ve[N];

int rand(int l, int r)
{
	uniform_int_distribution<int> uni(l, r);
	return uni(mt);
}

int trace(int u)
{
	return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
}

int connect(int u, int v)
{
	if ((u = trace(u)) == (v = trace(v)))
		return -1;
	if (dsu[u] > dsu[v])
		swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
	vector<int> tmp;
	for (int j = 1; j <= n; j++)
		if (con[u][j] == -1 || con[v][j] == -1)
			tmp.push_back(j);
	for (int &a : ve[u])
		for (int &b : ve[v])
			con[a][b] = con[b][a] = 1;
	for (int &b : ve[v])
		ve[u].push_back(b);
	ve[v].clear();
	for (int &a : ve[u])
		for (int &b : tmp)
			con[a][b] = con[b][a] = -1;
	if (-dsu[u] > n / 2)
		return u;
	return -1;
}

int FindBase(int _n)
{
	n = _n;
	for (int i = 0; i < n; i++)
	{
		dsu[i] = -1;
		ve[i] = {i};
		con[i][i] = 1;
	}
	for (int i = 1; i <= 600; i++)
	{
		int u, v, cnt = 0;
		do
		{
			u = rand(0, n - 1);
			v = rand(0, n - 1);
			cnt++;
		} while (con[u][v] != 0 && cnt <= 100);
		if (cnt > 100)
			break;
		u = trace(u); v = trace(v);
		int rt = CollectRelics(u, v);
		if (rt == -1)
		{
			for (int &a : ve[u])
				for (int &b : ve[v])
					con[a][b] = con[b][a] = -1;
		}
		else
		{
			connect(rt, u);
			int tmp = connect(rt, v);
			if (tmp >= 0)
				return tmp;
		}
	}
	for (int i = 0; i < n; i++)
		if (-dsu[i] > n / 2)
			return i;
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 768 KB Partially correct : C = 534
2 Partially correct 6 ms 640 KB Partially correct : C = 600
3 Partially correct 12 ms 768 KB Partially correct : C = 600
4 Correct 7 ms 640 KB Correct : C = 204
5 Partially correct 6 ms 640 KB Partially correct : C = 600
6 Partially correct 7 ms 640 KB Partially correct : C = 332
7 Correct 16 ms 768 KB Correct : C = 240
8 Correct 9 ms 768 KB Correct : C = 241
9 Partially correct 11 ms 768 KB Partially correct : C = 570
10 Correct 6 ms 640 KB Correct : C = 39
11 Incorrect 16 ms 768 KB Wrong
12 Correct 6 ms 640 KB Correct : C = 39
13 Correct 5 ms 512 KB Correct : C = 0
14 Partially correct 12 ms 816 KB Partially correct : C = 541
15 Correct 16 ms 768 KB Correct : C = 242
16 Correct 8 ms 640 KB Correct : C = 143
17 Correct 7 ms 768 KB Correct : C = 65
18 Partially correct 6 ms 768 KB Partially correct : C = 600
19 Partially correct 8 ms 640 KB Partially correct : C = 340
20 Partially correct 6 ms 768 KB Partially correct : C = 600
21 Correct 7 ms 768 KB Correct : C = 63
22 Partially correct 12 ms 768 KB Partially correct : C = 577
23 Correct 5 ms 384 KB Correct : C = 4
24 Correct 7 ms 640 KB Correct : C = 149
25 Partially correct 8 ms 768 KB Partially correct : C = 365
26 Partially correct 11 ms 768 KB Partially correct : C = 410
27 Correct 9 ms 768 KB Correct : C = 260