Submission #985777

#	Time	Username	Problem	Language	Result	Execution time	Memory
985777		Zbyszek99	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	176 ms	30292 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

vector<vector<int>> ans;
int n;
vector<int> graf1[1000];
bitset<1000> odw;
vector<vector<int>> p;
int tree[1000];
int pop_tree[1000];
int rep_t[1000];
int rep[1000];
int typ_pol[1000];
vector<int> cycle[1000];
vector<int> v_on_tree[1000];
int akttree = 0;

int find_(int v)
{
	if(rep[v] == v) return v;
	rep[v] = find_(rep[v]); return rep[v];
}

int union_(int a, int b, int a2, int b2)
{
	rep[find_(b)] = find_(a);
	if(typ_pol[find_(b)] == -1 || typ_pol[find_(a)] == -1)
	{
		typ_pol[find_(b)] = max(typ_pol[find_(b)],typ_pol[find_(a)]);
		typ_pol[find_(a)] = max(typ_pol[find_(b)],typ_pol[find_(a)]);
	}
	if(typ_pol[find_(b)] == -1)
	{
		typ_pol[find_(b)] = p[a2][b2];
		typ_pol[find_(a)] = p[a2][b2];
	}
	//cout << typ_pol[find_(a)] << " " << typ_pol[find_(b)] << " " << a2 << " " << b2 <<  " typy\n"; 
	if(typ_pol[find_(a)] != typ_pol[find_(b)] || p[a2][b2] != typ_pol[find_(a)])
	{
		return -1;
	}
	return 0;
}

void dfs(int v)
{
	odw[v] = 1;
 	tree[v] = akttree;
	v_on_tree[akttree].push_back(v);
	rep_t[akttree] = v;
	for(auto& it: graf1[v]) if(odw[it] == 0) dfs(it); 
}

int construct(vector<vector<int>> p2) {
	p = p2;
	n = (int)p.size();
	ans.resize(n);
	rep(i,n)
	{
		typ_pol[i] = -1;
		pop_tree[i] = -1;
		rep(j,n)
		ans[i].push_back(0);
		rep[i] = i;
	}
	rep(i,n) rep(j,n)
	{
		if(p[i][j] == 3) return 0;
		if(p[i][j] == 1 && i != j) graf1[i].push_back(j); 
	}
	rep(i,n)
	{
		if(odw[i] == 0) 
		{
			dfs(i);
			akttree++;
		}
	}
	rep(i,n) rep(j,n)
	{
		if(tree[i] == tree[j] && p[i][j] != 1) 
		{
			//cout << " zle tree\n";
			return 0;
		}
	}
	rep(i,n) rep(j,n)
	{
		if(p[i][j] >= 2 && tree[i] != tree[j]) 
		{
		//	cout << i << " " << j << " " << tree[i] << " " << tree[j] << " union\n";
			if(union_(tree[i],tree[j],i,j) == -1)
			{
				//cout << tree[i] << " " << tree[j] << " " << i << " " << j << " zle union\n"; 
				return 0;
			}
		}
	}
	rep(i,n)
	{
		if(pop_tree[tree[i]] != -1)
		{
			ans[i][pop_tree[tree[i]]] = 1;
			ans[pop_tree[tree[i]]][i] = 1;
		}
		pop_tree[tree[i]] = i;
	}
	rep(i,akttree)
	{
		rep(j,akttree)
		{
			if(find_(i) == find_(j) && i < j)
			{
				for(auto& it1: v_on_tree[i])
				{
					for(auto& it2: v_on_tree[j])
					{
						if(p[it1][it2] == 0 || p[it1][it2] == 1) return 0;
					}
				}
			}
		}
	}
	rep(i,akttree)
	{
		//cout << find_(i) << " " << rep_t[i]<< " find\n";
		cycle[find_(i)].push_back(rep_t[i]);
	}
	rep(i,n)
	{
		int ile = (int)cycle[i].size();
		
		if(ile == 0) continue;
		if(ile == 1) continue;
		//cout << ile << " " << i << " cycle\n";
		int typ = p[cycle[i][0]][cycle[i][1]];
		if(typ == 0)
		{
			//cout <<  " typ 0\n";
			return 0;
		}
		if(typ == 2)
		{
			if(ile < 3) 
			{
				//cout << " ile < 3\n";
				return 0;
			}
			for(int j = 0; j < ile-1; j++)
			{
				ans[cycle[i][j]][cycle[i][j+1]] = 1;
				ans[cycle[i][j+1]][cycle[i][j]] = 1;
			}
			ans[cycle[i][0]][cycle[i][ile-1]] = 1;
			ans[cycle[i][ile-1]][cycle[i][0]] = 1;
		}	
	}
	build(ans);
	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