Submission #304812

#	Time	Username	Problem	Language	Result	Execution time	Memory
304812		arthur_nascimento	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	272 ms	26232 KiB

supertrees

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

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

#define maxn 1010
#define pb push_back

int foi1[maxn];
int rep1[maxn];
int rep2[maxn];

vector<int> L1[maxn];
vector<int> L2[maxn];


vector<int> comp;
void dfs1(int v,int p){
	if(foi1[v]) return;
	foi1[v] = 1;
	rep1[v] = p;
	comp.pb(v);
	for(int i : L1[v])
		dfs1(i,p);
}

int foi2[maxn];


void dfs2(int v,int p){
	if(foi2[v]) return;
	foi2[v] = 1;
	rep2[v] = p;
	comp.pb(v);
	for(int i : L2[v]){
		if(rep1[i] == i)
			dfs2(i,p);
	}
}

int construct(std::vector<std::vector<int>> p) {

	int n = p.size();

	std::vector<std::vector<int>> answer;

	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		for(int j=0;j<n;j++){
			row[j] = 0;
			if(p[i][j] == 1)
				L1[i].pb(j);
			if(p[i][j] == 2)
				L2[i].pb(j);
			if(p[i][j] == 3)
				return 0;
		}
		answer.push_back(row);
	}

	for(int i=0;i<n;i++)
		if(!foi1[i]){
			comp.clear();
			dfs1(i,i);
			for(int j=1;j<(int)comp.size();j++)
				answer[comp[j-1]][comp[j]] = answer[comp[j]][comp[j-1]] = 1;
		}
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(rep1[i] == rep1[j] && p[i][j] != 1)
				return 0;

	for(int i=0;i<n;i++)
		if(!foi2[i] && rep1[i] == i){
			comp.clear();
			dfs2(i,i);
			if(comp.size() == 2) return 0;
			if(comp.size() > 1)
				for(int j=0;j<(int)comp.size();j++){
					int A = comp[j];
					int B = comp[(j+1)%comp.size()];
					answer[A][B] = answer[B][A] = 1;
				}
		}

	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			if(rep1[i] != rep1[j] && rep2[rep1[i]] == rep2[rep1[j]] && p[i][j] != 2)
				return 0;
			if(rep1[i] != rep1[j] && rep2[rep1[i]] != rep2[rep1[j]] && p[i][j] != 0)
				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: 4 / 4