Submission #300695

#	Time	Username	Problem	Language	Result	Execution time	Memory
300695		gs14004	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	296 ms	22300 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using llf = long double;
const int MAXN = 1505;

struct disj{
	int pa[MAXN];
	int sz[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
		fill(sz, sz + n + 1, 1);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	int getsz(int x){ return sz[find(x)]; }
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		sz[p] += sz[q];
		pa[q] = p; return 1;
	}
}disj, cx;

int n;

int construct(std::vector<std::vector<int>> a) {
	n = sz(a);
	disj.init(n);
	std::vector<std::vector<int>> answer(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(a[i][j] == 1) disj.uni(i, j);
			if(a[i][j] == 3) return 0;
		}
		answer[i].resize(n);
	}
	vector<int> v;
	for(int i=0; i<n; i++){
		if(disj.find(i) != i){
			answer[i][disj.find(i)] = 1;
			answer[disj.find(i)][i] = 1;
		}
		else v.push_back(i);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(a[i][j] != a[disj.find(i)][disj.find(j)]) return 0;
		}
	}
	cx.init(n);
	for(auto &i : v){
		for(auto &j : v){
			if(a[i][j] == 2){
				cx.uni(i, j);
			}
		}
	}
	vector<int> v2[MAXN];
	for(auto &i : v){
		if(cx.getsz(i) > 1) v2[cx.find(i)].push_back(i);
	}
	for(int i=0; i<n; i++){
		if(sz(v2[i]) && sz(v2[i]) <= 2) return 0;
		for(auto &x : v2[i]){
			for(auto &y : v2[i]){
				if(x != y && a[x][y] != 2) return 0;
			}
		}
		if(sz(v2[i])){
			for(int j=0; j<sz(v2[i]); j++){
				int l = v2[i][j];
				int r = v2[i][(j+1)%sz(v2[i])];
				answer[l][r] = answer[r][l] = 1;
			}
		}
	}
	disj.init(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(answer[i][j]) disj.uni(i, j);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(a[i][j] == 0 && disj.find(i) == disj.find(j)) 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