IOI 2020 – Contest Day 1- Supertrees Problem and Solution

IOI 2020 – Contest Day 1- Supertrees Problem and Solution

The 32nd International Olympiad in Informatics was held in Online in 2020. There were two competition days, with 3 tasks given to the competitors on each day. You can see Supertrees Problem and Solution below.

Problem :

day1-supertrees-ISC

Solution :

#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;
}

 147 total views,  1 views today

Post Disclaimer

the above hole problem statement is given by hackerrank.com but the solution is generated by the SLTECHACADEMY authority if any of the query regarding this post or website fill the following contact form thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *