Submission #1042048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042048		amine_aroua	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	121 ms	27480 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);
	bool b = 0;
	for(int i = 0 ; i < nn ;i++)
	{
		for(int j = 0 ; j < nn ; j++)
		{
		    if(pp[i][j] == 3)
		        b = 1;
			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] >= 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;
		map<int , vector<int>> trees;
		for(auto i : c)
		{
			int par = maker.get(i);
			trees[par].push_back(i);
			if(i == par)
			{
				v.push_back(i);
				continue;
			}
			adj[par][i] = 1;
			adj[i][par] = 1;
		}
		set<int> s;
		for(auto &x : trees)
		{
			for(auto &y : trees)
			{
				if(x.first == y.first)
					continue;
				for(auto &z : x.second)
				{
					for(auto &w : y.second)
					{
						s.insert(pp[z][w]);
					}
				}
			}
		}
		if(s.empty())
		{
		    if(b)
		        return 0;
		    else
		        continue;
		}
		if((int)s.size() > 1 || *s.begin() < 2)
		{
			return 0;
		}
		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;
		}
		if(*s.begin() == 3 && v.size() == 3)
		{
			return 0;
		}		
		if(*s.begin() == 3)
		{adj[v[0]][v[2]] = 1;
		adj[v[2]][v[0]] = 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();
}

Compilation message (stderr)

supertrees.cpp: In function 'bool check_conn()':
supertrees.cpp:43:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |       if(pp[i][j] == 3)
      |       ^~
supertrees.cpp:45:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   45 |    if(pp[i][j])
      |    ^~

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