Submission #531889

#	Time	Username	Problem	Language	Result	Execution time	Memory
531889		EqualTurtle	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	228 ms	22212 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define v2d vector <vector <int> >
using namespace std;

constexpr int MAXN = 1e3 + 7;

int siz[MAXN];
int repl[MAXN];
int repl2[MAXN];
int repr[MAXN];
int rep[MAXN];
int type[MAXN];

void debug(int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << i << " " << rep[i] << " " << repl[i] << " " << repl2[i] << " " << repr[i] << " " << type[i] << " " << siz[i] << "\n";
	}
	cout << "-----------------------------\n";
}

int Find(int a){
	return rep[a] == a ? a : rep[a] = Find(rep[a]);
}

void Union(int a, int b, bool how){
	if (Find(a) == Find(b))
		return;
	if (how){
		repl2[Find(b)] = min(repl2[Find(a)], min(repl2[Find(b)], max(repl[Find(b)], repl[Find(a)])));
		repl[Find(b)] = min(repl[Find(a)], repl[Find(b)]);
		repr[Find(b)] = max(repr[Find(b)], repr[Find(a)]);
		siz[Find(b)] += siz[Find(a)];
		rep[Find(a)] = Find(b);
	}
	rep[Find(a)] = Find(b);
}


int construct(v2d p) 
{
	int n = p.size();
	v2d answer;
	for (int i = 0; i < n; i++){
		vector<int> cv;
		for (int j = 0; j < n; j++)
			cv.push_back(0);
		answer.push_back(cv);
	}
	
	for (int i = 0; i < n; i++){
		rep[i] = i;
		repl[i] = i;
		repl2[i] = MAXN;
		repr[i] = i;
		siz[i] = 1;
	}

	//debug(n);

	for (int i = 0; i < n; i++){
		if (p[i][i] != 1)
			return 0;
		for (int j = i + 1; j < n; j++)
		{
			if (p[i][j] != p[j][i] || p[i][j] == 3)
				return 0;

			if (p[i][j] == 1){
				if (p[i] != p[j])
					return 0;
				if (Find(i) != Find(j)){
					Union(i, j, false);
					answer[i][j] = 1;
					answer[j][i] = 1;
				}
			}
		}
	}

	//debug(n);

	for (int i = 0; i < n; i++){
		if (i != Find(i))
			continue;
		for (int j = i + 1; j < n; j++)
		{
			if (j != Find(j))
				continue;
			if (p[i][j] == 2 || p[i][j] == 3)
			{
				if (type[i] == 0)
					type[i] = p[i][j];
				else if (type[i] != p[i][j])
					return 0;

				if (type[j] == 0)
					type[j] = p[i][j];
				else if (type[j] != p[i][j])
					return 0;
				
				for (int k = 0; k < n; k++)
				{
					if (p[i][k] == 0){
						if (p[j][k] != 0)
							return 0;
					}
					else if (p[i][k] == 1){
						if (p[j][k] != p[i][j])
							return 0;
					}
					else{
						if (p[j][k] != p[i][j] && p[j][k] != 1)
							return 0;
					}
				}

				if (Find(i) != Find(j)){
					answer[repr[Find(i)]][repr[Find(j)]] = 1;
					answer[repr[Find(j)]][repr[Find(i)]] = 1;
					Union(i, j, true);
				}
			}
		}
	}

	//debug(n);

	for (int i = 0; i < n; i++){
		if (type[Find(i)] != 0)
		{		
			if (siz[Find(i)] < 3)
				return 0;
			answer[repr[Find(i)]][repl[Find(i)]] = 1;
			answer[repl[Find(i)]][repr[Find(i)]] = 1;

			if (type[Find(i)] == 3)
			{
				if (siz[Find(i)] < 4)
					return 0;
				answer[repl2[Find(i)]][repr[Find(i)]] = 1;
				answer[repr[Find(i)]][repl2[Find(i)]] = 1;
			}

			type[Find(i)] = 0;
		}
	}
	
	//debug(n);
	build(answer);
	return 1;
}

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