Submission #302085

#	Time	Username	Problem	Language	Result	Execution time	Memory
302085		arthurconmy	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	254 ms	26360 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;

#ifndef ARTHUR_LOCAL
	#include "supertrees.h"
#endif

#define len(x) int((x).size())

#ifdef ARTHUR_LOCAL
	void build(vector<vector<int>> V)
	{
		for(auto row:V)
		{
			for(auto thing:row) cout << thing << " ";
			cout << endl;
		}
	}
#endif

vector<int> comp;
vector<int> adj[1001];
bool vis[1001];

void dfs(int v)
{
	vis[v]=1;
	comp.push_back(v);

	for(auto u:adj[v])
	{
		if(vis[u]) continue;
		dfs(u);
	}
}

int construct(vector<vector<int>> P) {
	int n = (int)P.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) 
	{
		vector<int> row(n);
		answer.push_back(row);
	}

	for(int i=0; i<n; i++)
	{
		for(int j=i+1; j<n; j++)
		{
			if(P[i][j] == 1)
			{
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}

	vector<int> heads;
	vector<vector<int>> headcomps;

	for(int i=0; i<n; i++)
	{
		if(vis[i]) continue;
		comp.clear();
		dfs(i);

		int m = (int)comp.size();
		heads.push_back(i);
		headcomps.push_back(comp);

		for(int i=0; i<m; i++)
		{
			for(int j=i+1; j<m; j++)
			{
				if(P[comp[i]][comp[j]] != 1) return 0;
			}
		}

		for(int i=1; i<m; i++)
		{
			answer[comp[0]][comp[i]]=1;
			answer[comp[i]][comp[0]]=1;
			// answer[comp[i]][comp[(i+1)%m]]=1;
			// answer[comp[(i+1)%m]][comp[i]]=1;
		}
	}

	vector<bool> headvis(n+1);

	for(int i=0; i<len(heads); i++)
	{
		if(headvis[i]) continue;
		headvis[i]=1;

		vector<int> cur = {heads[i]};

		for(int j=i+1; j<len(heads); j++)
		{
			if(P[heads[i]][heads[j]] == 2)
			{
				cur.push_back(heads[j]);
				headvis[j]=1;
			}
		}

		// for(auto c:cur) cout << c << " ";
		// cout << endl;

		if(len(cur)<=2) continue;
		for(int j=0; j<len(cur); j++)
		{
			answer[cur[j]][cur[(j+1)%len(cur)]]=1;			
			answer[cur[(j+1)%len(cur)]][cur[j]]=1;
		}
	}

	build(answer);
	return 1;
}

#ifdef ARTHUR_LOCAL
int main()
{
	construct({{1,2,2,0},{2,1,2,0},{2,2,1,0},{0,0,0,1}});
}
#endif

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