Submission #1042069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042069		amine_aroua	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	149 ms	27584 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> pp;
vector<vector<int>> adj;
int nn;
struct DSU
{
	vector<int> e;
	DSU(int _n)
	{
		e.assign(_n , -1);
	}	
	
	int get(int u )
	{
		return (e[u] < 0 ? u : e[u] = get(e[u]));
	}
	bool same(int u , int v)
	{
		return get(u) == get(v);
	}
	void unite(int u , int v)
	{
		u = get(u) , v = get(v);
		if(u == v)
			return;
		if(e[u] > e[v])
			swap(u , v);
		e[u]+=e[v];
		e[v] = u;
	}
};
bool check_conn()
{
	DSU dsu(nn);
	for(int i = 0 ; i < nn ;i++)
	{
		for(int j = 0 ; j < nn ; j++)
		{
			if(pp[i][j])
			{
				dsu.unite(i , j);
			}
		}
	}
	for(int i = 0 ; i < nn ; i++)
	{
		for(int j = 0 ; j <  nn; j++)
		{
			if(pp[i][j] == 0 && dsu.same(i , j))
			{
				return 0;
			}
		}
	}
	DSU maker(nn);
	for(int i = 0 ; i < nn ;i++)
	{
		for(int j = 0 ; j < nn ;j++)
		{
			if(pp[i][j] == 1)
			{
				maker.unite(i , j);
			}
		}
	}
	for(int i = 0 ; i < nn ; i++)
	{
		for(int j = 0 ; j < nn ; j++)
		{
          	if(pp[i][j] == 3)
              	return 0;
			if(pp[i][j] >= 2 && maker.same(i , j))
			{
				return 0;
			}
		}
	}
	vector<vector<int>> comp(nn);
	for(int i = 0 ; i < nn ; i++)
	{
		comp[dsu.get(i)].push_back(i);
	}
	for(auto c : comp)
	{
		vector<int> v;
		for(auto i : c)
		{
			int par = maker.get(i);
			if(i == par)
			{
				v.push_back(i);
				continue;
			}
			adj[par][i] = 1;
			adj[i][par] = 1;
		}
		if((int)v.size() == 1)
			continue;
		if((int)v.size() == 2)
		{
			return 0;
		}
		for(int i = 0 ; i < (int)v.size() ; i++)
		{
			adj[v[i]][v[(i + 1)%((int)v.size())]] = 1;
			adj[v[(i + 1)%((int)v.size())]][v[i]] = 1;
		}
	}
	build(adj);
	return 1;
}
int construct(std::vector<std::vector<int>> P) {
	
	pp = P;
	nn = (int)pp.size();
	adj.assign(nn , vector<int>(nn));
	return check_conn();
}

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