Submission #1291657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291657		julia_08	Connecting Supertrees (IOI20_supertrees)	C++20	46 / 100	105 ms	26260 KiB

supertrees

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

using namespace std;

const int MAXN = 1e3 + 10;

int marc[MAXN];

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();

	// 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){

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

	}

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

	}

	for(int i=0; i<n; i++){
		if(!marc[i]){

			vector<int> cur;

			for(int j=0; j<n; j++){
				if(!marc[j] && p[i][j] > 0){
					cur.push_back(j);
				}
			}

			for(auto j : cur) marc[j] = 1;

			if(!solve(cur)) return 0;

		}
	}

	build(b);

	return 1;

}

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