Submission #301134

#	Time	Username	Problem	Language	Result	Execution time	Memory
301134		ElyesChaabouni	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	286 ms	22236 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int anc[200000], anc1[200000];
void get_anc(int x)
{
	if(x==-1)
		return;
	int cu=anc[x];
	while(cu!=anc[cu])
		cu=anc[cu];
	anc[x]=cu;
}
void unite(int x, int y)
{
	get_anc(x);
	get_anc(y);
	if(anc[x]==anc[y])
		return;
	anc[anc[y]]=anc[x];
	anc[y]=anc[x];
}
void get_anc1(int x)
{
	int cu=anc1[x];
	while(cu!=anc1[cu])
		cu=anc1[cu];
	anc1[x]=cu;
}
void unite1(int x, int y)
{
	get_anc1(x);
	get_anc1(y);
	anc1[anc1[y]]=anc1[x];
	anc1[y]=anc1[x];
}
/*void build(vector<vector<int> >x)
{
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
			cout << x[j][i] << ' ';
		cout << '\n';
	}
}*/
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			ans[i][j]=0;
	for(int i = 0; i < n; i++)
		anc[i]=i;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j]==1)
				unite(i, j);
		}
	}
	for(int i = 0; i < n; i++)
	{
		get_anc(i);
		//cout << anc[i] << ' ';
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(((anc[i]==anc[j]) && (p[i][j]!=1)) || ((anc[i]!=anc[j]) && (p[i][j]==1)))
				return 0;
			if(p[i][j]==3)
				return 0;
		}
	}
	for(int i = 0; i < n; i++)
	{
		vector<int>v;
		for(int j = 0; j < n; j++)
		{
			if(anc[j]==i)
				v.push_back(j);
		}
		for(int j = 0; j < ((int)(v.size()))-1; j++)
		{
			ans[v[j]][v[j+1]]=1;
			ans[v[j+1]][v[j]]=1;
		}
	}
	for(int i = 0; i < n; i++)
		anc1[i]=-1;
	for(int i = 0; i < n; i++)
	{
		bool found=0;
		for(int j = 0; j < n && !found; j++)
		{
			if(anc[j]==i)
				found=1;
		}
		if(found)
			anc1[i]=i;
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j]==2)
			{
				get_anc(i);
				get_anc(j);
				unite1(anc[i], anc[j]);
			}
		}
	}
	for(int i = 0; i < n;i++)
		get_anc1(i);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j]==0 && anc1[anc[i]] == anc1[anc[j]] && anc1[anc[i]]!=-1)
				return 0;
		}
	}
	for(int i = 0; i < n; i++)
	{
		vector<int>v;
		for(int j = 0; j < n; j++)
		{
			if(anc1[j]==i)
				v.push_back(j);
		}
		for(int j = 0; j < ((int)(v.size()))-1; j++)
		{
			ans[v[j]][v[j+1]]=1;
			ans[v[j+1]][v[j]]=1;
		}
		if(v.size() == 2)
			return 0;
		if(v.size() > 2)
		{
			ans[v[0]][v.back()]=1;
			ans[v.back()][v[0]]=1;
		}
	}
	for(int i = 0; i < n; i++)
		ans[i][i]=0;
	build(ans);
	return 1;
}
/*int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	vector<vector<int> >a;
	int n;
	cin >> n;
	for(int i = 0; i < 2; i++)
	{
		vector<int>x;
		x.resize(2);
		a.push_back(x);
	}
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			cin >> a[i][j];
	cout << construct(a) << '\n';
}*/

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