Submission #1142787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142787		PagodePaiva	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	129 ms	30200 KiB

supertrees

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

using namespace std;

const int N = 1010;
vector <int> g[N][2];
vector <vector <int>> componentes;
int mark[N];
vector <int> aux;

void dfs(int v){
	if(mark[v]) return;
	mark[v] = 1;
	aux.push_back(v);
	for(int i = 0;i < 2;i++){
		for(auto x : g[v][i]){
			dfs(x);
		}
	}
	return;
}

int ans[N][N];

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			if(i == j) continue;
			if(p[i][j] == 0) continue;
			if(p[i][j] == 3) return 0;
			g[i][p[i][j]-1].push_back(j);
		}
	}
	for(int i = 0;i < n;i++){
		if(mark[i]) continue;
		dfs(i);
		componentes.push_back(aux);
		aux.clear();
	}
	memset(mark, 0, sizeof mark);
	for(auto vertices : componentes){
		vector <int> rep;
		for(auto v : vertices){
			for(auto u : vertices){
				if(p[u][v] == 0) return 0;
			}
		}
		for(auto v : vertices){
			if(mark[v]) continue;
			for(auto x : g[v][0]){
				for(auto y : g[v][0]){
					if(p[x][y] != 1){
						return 0;
					}
					if(g[x][0].size() != g[y][0].size()){
						return 0;
					}
				}
			}
			int ant = v;
			for(auto x : g[v][0]){
				ans[ant][x] = ans[x][ant] = 1;
				ant = x;
				mark[x] = 1; 
			}
			mark[v] = 1;
			rep.push_back(v);
		}
		if(rep.size() == 2) return 0;
		if(rep.size() == 1) continue;
		rep.push_back(rep[0]);
		for(int i = 1;i < rep.size();i++){
			int a = rep[i], b = rep[i-1];
			ans[a][b] = ans[b][a] = 1;
		}
	}
	vector <vector <int>> resposta;
	for(int i = 0;i < n;i++){
		vector <int> penis;
		for(int j = 0;j < n;j++){
			penis.push_back(ans[i][j]);
		}
		resposta.push_back(penis);
	}
	build(resposta);
	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