Submission #300362

#	Time	Username	Problem	Language	Result	Execution time	Memory
300362		faustaadp	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	262 ms	26232 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 1e3 + 5;
ll n, bisa = 1, p[NN], x[NN];
std::vector<std::vector<int>> answer;
vector<ll> v[NN];
std::vector<std::vector<int>> px;
ll car(ll pos)
{
	if(p[pos] == pos)
		return pos;
	else
		return p[pos] = car(p[pos]);
}
int construct(std::vector<std::vector<int>> pt) {
	px = pt;
	n = px.size();
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n, 0);
		answer.push_back(row);
	}
	for (int i = 0; i < n; i++) 
		p[i] = i;
	for (int i = 0; i < n; i++) 
		for (int j = i + 1; j < n; j++) 
			if(px[i][j])
				p[car(i)] = car(j); 
	for (int i = 0; i < n; i++) 
		v[car(i)].pb(i);
	for (int i = 0; i < n; i++) 
	{
		if(!bisa)
			break;
		ll sz = v[i].size();
		x[0] = 0;
		x[1] = 0;
		x[2] = 0;
		x[3] = 0;
		for(ll j = 0; j < sz; j++)
			for(ll k = j + 1; k < sz; k++)
				x[px[v[i][j]][v[i][k]]] = 1;
		if(x[0] + x[1] + x[2] + x[3] == 0) 
			continue;
		else
		if(x[0])
			bisa = 0;
		else
		if(x[2] == 1 && x[3] == 1)
			bisa = 0;
		else
		if(x[1] == 1 && x[2] == 0 && x[3] == 0)
		{
			for(ll j = 1; j < sz; j++)
			{
				answer[v[i][j - 1]][v[i][j]] = 1;
				answer[v[i][j]][v[i][j - 1]] = 1;
			}
		}
		else
		if(x[2] == 1 && x[1] == 0)
		{
			if(sz <= 2)
				bisa = 0;
			else
			{
				for(ll j = 0; j < sz; j++)
				{
					answer[v[i][j]][v[i][(j + 1) % sz]] = 1;
					answer[v[i][(j + 1) % sz]][v[i][j]] = 1;
				}
			}
		}
		else
		if(x[3] == 1 && x[1] == 0)
		{
			if(sz <= 3)
				bisa = 0;
			else
			{
				for(ll j = 0; j < sz; j++)
				{
					answer[v[i][j]][v[i][(j + 1) % sz]] = 1;
					answer[v[i][(j + 1) % sz]][v[i][j]] = 1;
				}
				answer[v[i][1]][v[i][sz - 1]] = 1;
				answer[v[i][sz - 1]][v[i][1]] = 1;
			}
		}
		else
		if(x[2] == 1 && x[1] == 1)
		{
			vector<ll> sat, dua;
			for(ll j = 0; j < sz; j++)
			{
				ll mi = 4;
				for(ll k = 0; k < sz; k++)
				{
					if(j == k)
						continue;
					mi = min(mi, (ll)px[v[i][j]][v[i][k]]);
				}
				if(mi == 2)
					dua.pb(v[i][j]);
				else
					sat.pb(v[i][j]);
			}
			ll ss = sat.size();
			ll sd = dua.size();
			// cout << ss << " " << sd << "_\n";
			for(ll j = 1; j < ss; j++)
			{
				answer[sat[j - 1]][sat[j]] = 1;
				answer[sat[j]][sat[j - 1]] = 1;
			}
			for(ll j = 1; j < sd; j++)
			{
				answer[dua[j - 1]][dua[j]] = 1;
				answer[dua[j]][dua[j - 1]] = 1;
			}
			answer[sat[0]][dua[0]] = 1;
			answer[dua[0]][sat[0]] = 1;
			answer[sat[0]][dua[sd - 1]] = 1;
			answer[dua[sd - 1]][sat[0]] = 1;
		}
	}
	if(!bisa)return 0;
	build(answer);
	return 1;
}

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