Submission #1187677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187677		hamzabc	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	133 ms	22180 KiB

supertrees

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


using namespace std;


vector<int> d1e, d2e, d2b;  // DSU1 end, DSU2 end, DSU2 begin
vector<int> DSU1, DSU2;


int goDSU(int a, vector<int> &DSU){
	if (a == DSU[a]){
		return a;
	}
	DSU[a] = goDSU(DSU[a], DSU);
	return DSU[a];
}


int construct(vector<vector<int>> p) {
	int n = p.size();
	DSU1.resize(n);
	DSU2.resize(n);
	d1e.resize(n, -1);
	d2b.resize(n, -1);
	d2e.resize(n, -1);
	for (int i = 0; i < n; i++){
		DSU1[i] = i;
		DSU2[i] = i;
	}
	vector<vector<int>> answer(n, vector<int>(n));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] == 3){
				return 0;
			}
			if (p[i][j] == 1){
				DSU1[goDSU(i, DSU1)] = goDSU(j, DSU1);
			}
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] != 1 && goDSU(i, DSU1) == goDSU(j, DSU1)){
				return 0;
			}
		}
	}
	for (int i = 0; i < n; i++){
		if (d1e[goDSU(i, DSU1)] == -1){
			d1e[goDSU(i, DSU1)] = i;
		}else{
			answer[d1e[goDSU(i, DSU1)]][i] = 1;
			answer[i][d1e[goDSU(i, DSU1)]] = 1;
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] == 2){
				DSU2[goDSU(goDSU(i, DSU1), DSU2)] = goDSU(goDSU(j, DSU1), DSU2);
			}
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] == 0 && goDSU(goDSU(i, DSU1), DSU2) == goDSU(goDSU(j, DSU1), DSU2)){
				return 0;
			}
		}
	}
	for (int i = 0; i < n; i++){
		if (i != goDSU(i, DSU1))
		continue;
		if (d2e[goDSU(i, DSU2)] == -1){
			d2e[goDSU(i, DSU2)] = i;
			d2b[goDSU(i, DSU2)] = i;
		}else{
			answer[d2e[goDSU(i, DSU2)]][i] = 1;
			answer[i][d2e[goDSU(i, DSU2)]] = 1;
			d2e[goDSU(i, DSU2)] = i;
		}
	}
	for (int i = 0; i < n; i++){
		if (i != goDSU(goDSU(i, DSU1), DSU2)){
			continue;
		}
		if (d2e[i] == d2b[i])
			continue;
		if (answer[d2e[i]][d2b[i]]){
			return 0;
		}
		answer[d2e[i]][d2b[i]] = 1;
		answer[d2b[i]][d2e[i]] = 1;
	}
	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