Submission #1306844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306844		peteza	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	115 ms	22184 KiB

supertrees

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

int n;
vector<int> par;

int fpar(int x) {
	return x == par[x] ? x : par[x]  =fpar(par[x]);
}

vector<vector<int>> splits(vector<vector<int>>&p, vector<int> scope, int mode) {
	for(int i:scope) {
		for(int j:scope) {
			if(p[i][j] == mode) continue;
			if(fpar(i) == fpar(j)) continue;
			par[fpar(i)] = fpar(j);
		}
	}
	vector<bool> vis(n, 0);
	vector<vector<int>> toret;
	for(int i:scope) {
		for(int j:scope) {
			if(fpar(i) == fpar(j) && p[i][j] == mode) return {};
			if(fpar(i) != fpar(j) && p[i][j] != mode) return {};
		}
	}
	for(int i:scope) {
		if(vis[fpar(i)]) continue;
		vis[fpar(i)] = 1;
		toret.push_back({});
		for(int j:scope) {
			if(fpar(i) == fpar(j)) toret.back().push_back(j);
		}
	}
	return toret;
}

int construct(vector<vector<int>> p) {
	n = p.size();
	vector<vector<int>> answer;
	int cmx = 0;
	vector<int> og(n);
	iota(og.begin(), og.end(), 0);
	for (int i = 0; i < n; i++) {
		vector<int> row(n, 0);
		answer.push_back(row);
		cmx = max(cmx, *max_element(p[i].begin(), p[i].end()));
	}
	
	if(cmx >= 3) return 0;
	par.resize(n);
	iota(par.begin(), par.end(), 0);
	auto r1 = splits(p, og, 0);
	if(r1.empty()) return 0;
	
	par.resize(n);
	iota(par.begin(), par.end(), 0);
	for(auto &e:r1) {
		auto r2 = splits(p, e, 2);
		if(r2.empty()) return 0;
		for(int i=0;i<r2.size()-1;i++) {
			//cout << e.front() << '\n';
			cout << r2[i].front() << ' ' << r2[i+1].front() << '\n';
			answer[r2[i].front()][r2[i+1].front()] = answer[r2[i+1].front()][r2[i].front()] = 1;
		}
		if(r2.size() > 1) answer[r2[0].front()][r2.back().front()] = answer[r2.back().front()][r2[0].front()] = 1;
		for(auto &e:r2) {
			for(int i=1;i<e.size();i++) {
				answer[e[i]][e[i-1]] = answer[e[i-1]][e[i]] = 1;
			}
		}
	}
	build(answer);

	return 1;
}

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