Submission #302038

#	Time	Username	Problem	Language	Result	Execution time	Memory
302038		arthurconmy	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	257 ms	26232 KiB

supertrees

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

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

#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);
			}
		}
	}

	for(int i=0; i<n; i++)
	{
		comp.clear();
		dfs(i);

		int m = (int)comp.size();

		// for(au)

		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;
		}
	}

	build(answer);
	return 1;
}

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

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