Submission #441093

#	Time	Username	Problem	Language	Result	Execution time	Memory
441093		roseanne_pcy	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	254 ms	22328 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); }

vector<int> par;
vector<int> subpar;
vector< vector<int> > res;
vector<int> bucks[maxn];
vector<int> subbucks[maxn];

void init(vector<int> &p)
{
	for(int i = 0; i< (int) p.size(); i++) p[i] = i;
}

int findset(vector<int> &p, int x)
{
	if(p[x] == x) return x;
	return p[x] = findset(p, p[x]);
}

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

void addedge(int u, int v)
{
	res[u][v] = res[v][u] = 1;
}

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

	par = vector<int>(n, 0);
	subpar = vector<int>(n, 0);
	res.assign(n, vector<int>(n, 0));

	init(par); init(subpar);

	bool good = true;

	for(int i = 0; i< n; i++)
	{
		for(int j = i+1; j< n; j++)
		{
			if(p[i][j] > 0)
			{
				if(p[i][j] == 3) return 0;
				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;
				}
			}
		}
	}

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

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

	for(int i = 0; i< n; i++)
	{
		if(findset(subpar, i) != i)
		{
			addedge(findset(subpar, i), i);
		}
		else bucks[findset(par, i)].pb(i);

		subbucks[findset(subpar, i)].pb(i);
	}

	for(int i = 0; i< n; i++)
	{
		if((int) bucks[i].size() <= 1) continue;
		if((int) bucks[i].size() == 2) return 0;

		int val = -1;

		for(int j = 0; j< (int) bucks[i].size(); j++)
		{
			for(int k = j+1; k< (int) bucks[i].size(); k++)
			{
				int u = bucks[i][j], v = bucks[i][k];
				for(int su : subbucks[u])
				{
					for(int sv : subbucks[v])
					{
						if(val == -1) val = p[su][sv];
						else if(val != p[su][sv]) return 0;
					}
				}
			}
		}

		for(int j = 0; j+1< (int) bucks[i].size(); j++)
		{
			addedge(bucks[i][j], bucks[i][j+1]);
		}
		addedge(bucks[i][0], bucks[i].back());
		if(val == 3 && bucks[i].size() == 3) return 0;
		if(val == 3) addedge(bucks[i][0], bucks[i][2]);
	}

	build(res);
	return 1;
}

Compilation message (stderr)

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

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