Submission #1291651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291651		julia_08	Connecting Supertrees (IOI20_supertrees)	C++20	11 / 100	106 ms	26200 KiB

supertrees

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

using namespace std;

const int MAXN = 1e3 + 10;

int p[MAXN][MAXN];

vector<vector<int>> b;

void add(int u, int v){

	b[u][v] = b[v][u] = 1;

}

bool solve(vector<int> &cur){

	int n = (int) cur.size();

	if(n == 0) return true;

	// sei que ta todo mundo na mesma comp

	vector<int> cycle;

	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			if(p[cur[i]][cur[j]] == 2){
				cycle = {cur[i], cur[j]};
			}
		}
	}

	if(cycle.empty()){

		// entao todo mundo eh 1

		for(int i=1; i<n; i++) add(cur[i - 1], cur[i]);

		return true;

	}

	for(int i=0; i<n; i++){

		if(cur[i] == cycle[0] || cur[i] == cycle[1]) continue;

		bool ok = true;

		for(auto x : cycle){
			if(p[cur[i]][x] != 2){
				ok = false;
			}
		}

		if(ok) cycle.push_back(cur[i]);

	}

	if((int) cycle.size() < 3) return false;

	for(int i=1; i<cycle.size(); i++) add(cycle[i - 1], cycle[i]);

	add(cycle.back(), cycle[0]);

	for(auto x : cycle){

		vector<int> group;

		for(int i=0; i<n; i++){
			if(p[cur[i]][x] == 1 && x != cur[i]){
				group.push_back(cur[i]);
			}
		}

		if(!group.empty()) add(group[0], x);

		if(!solve(group)) return false;

	}

	return true;

}

int construct(vector<vector<int>> p_){

	int n = (int) p_.size();

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			p[i][j] = p_[i][j];
		}
	}

	for(int i=0; i<n; i++){

		b.push_back({});

		for(int j=0; j<n; j++) b.back().push_back(0);

	}

	vector<int> cur;

	for(int i=0; i<n; i++){
		if(cur.empty() || p[i][cur.back()] > 0){

			cur.push_back(i);

		} else{

			if(!solve(cur)) return 0;

			cur = {i};

		}
	}

	if(!solve(cur)) return 0;

	build(b);

	return 1;

}

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