Submission #440872

#	Time	Username	Problem	Language	Result	Execution time	Memory
440872		roseanne_pcy	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	246 ms	24056 KiB

supertrees

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef long long ll;

#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int md = 1e9+7;
const ll inf = 1e18;
const int maxn = 1e3+5;

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

int par[maxn];

void init(int *p, int n)
{
	for(int i = 0; i< n; i++) p[i] = i;
}

int findset(int *p, int x)
{
	if(p[x] == x) return x;
	return p[x] = findset(p, p[x]);
}

void unionset(int *p, int x, int y)
{
	int a = findset(p, x);
	int b = findset(p, y);
	if(a == b) return;
	p[a] = b;
}

int construct(std::vector<std::vector<int>> p) 
{
	int n = p.size();

	init(par, n);

	bool good = true;

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			if(p[i][j] == 1)
			{
				unionset(par, i, j);
			}
		}
	}

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			if(p[i][j] == 0)
			{
				if(findset(par, i) == findset(par, j))
				{
					return 0;
				}
			}
		}
	}

	vector< vector<int> > res(n, vector<int>(n, 0));

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			res[i][j] = res[j][i] = (findset(par, i) == j);
		}
	}

	build(res);
	return 1;

}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:7: warning: unused variable 'good' [-Wunused-variable]
   56 |  bool good = true;
      |       ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4