Submission #434609

#	Time	Username	Problem	Language	Result	Execution time	Memory
434609		frodakcin	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	306 ms	22284 KiB

supertrees

#include "supertrees.h"
#include <algorithm>
#include <vector>

struct DSU
{
	public:
		std::vector<int> p, r;
		DSU(int N): p(N, -1), r(N, 0) {}
		int find(int n) {return p[n] == -1 ? n : p[n] = find(p[n]);}
		bool merge(int u, int v)
		{
			u=find(u), v=find(v);
			if(u==v) return 0;
			if(r[u] < r[v]) std::swap(u, v);
			p[v]=u, r[u]+=r[u]==r[v], r[v]=-1;
			return 1;
		}
};

int construct(std::vector<std::vector<int>> p)
{
	int N = p.size();
	std::vector<std::vector<int>> answer(N, std::vector<int>(N, 0));

	DSU dsu1(N);
	for (int i = 0; i < N; i++)
		for(int j=i+1;j<N;++j)
			if(p[i][j]==1)
			{
				if(dsu1.merge(i, j))
				{
					if(p[i] != p[j]) // must have identical adj lists
						return 0;
					answer[i][j]=1; // this makes a tree among all 1-con components
					answer[j][i]=1;
				}
			}
	std::vector<int> head;
	for(int i=0;i<N;++i) if(dsu1.p[i]==-1) head.push_back(i);

	for(int i=0;i<N;++i)
	{
		bool s2=0, s3=0;
		for(int x:p[i])
			if(x==2) s2=1;
			else if(x==3) s3=1;
		if(s2 && s3) return 0;
	}

	for(int sz: {2,3}) // handle 2/3 case
	{
		std::vector<std::vector<int>> group(N, std::vector<int>());
		DSU dsu2(N);
		for(int i=0;i<(int)head.size();++i)
			for(int j=i+1;j<(int)head.size();++j)
				if(p[head[i]][head[j]]==sz)
					dsu2.merge(head[i], head[j]);
		for(int i=0;i<N;++i)
			group[dsu2.find(i)].push_back(i);
		for(int i=0;i<N;++i)
			if(group[i].size() >= 2)
			{
				if(group[i].size() <= 2) return 0;
				if(sz == 3 && group[i].size() <= 4) return 0;
				for(int j=0;j<(int)group[i].size();++j) // create a simple cycle
				{
					int u=group[i][j], v=group[i][(j+1)%group[i].size()];
					answer[u][v]=answer[v][u]=1;
				}
				if(sz == 3)
					answer[group[i][0]][group[i][2]]=answer[group[i][2]][group[i][0]]=1;

				//identicality test
				for(int j=0;j<(int)group[i].size();++j)
					for(int k=j+1;k<(int)group[i].size();++k)
						if(p[group[i][j]][group[i][k]] != sz)
							return 0;
			}
	}

	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: 0 / 4