Submission #1259134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259134		altern23	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	0 ms	328 KiB

supertrees

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

#define ll long long

struct DSU{
	ll N;
	vector<ll> par;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5);
		iota(par.begin(), par.end(), 0LL);
	}
	ll find(ll idx){
		return par[idx] == idx ? idx : par[idx] = find(par[idx]);
	}
	void join(ll a, ll b){
		a = find(a), b = find(b);
		if(a == b) return;
		par[b] = a;
	}
};

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n));
	// check ada 3 ato ga
	bool ok = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			ok &= (p[i][j] != 3);
		}
	}

	if(!ok) return 0;

	// merge dulu yang 1
	DSU dsu1(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 1) dsu1.join(i, j);
		}
	}

	// check connectivity
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			ok &= (p[i][j] == p[dsu1.find(i)][j]);
		}
	}

	if(!ok) return 0;

	DSU dsu2(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 2){
				dsu2.join(dsu1.find(i), dsu1.find(j));
			}
		}
	}

	// check connectivity
	for(int i = 0; i < n; i++){
		if(dsu1.find(i) != i) continue;
		for(int j = 0; j < n; j++){
			if(dsu2.find(j) == dsu2.find(i)){
				if(dsu1.find(j) == i) ok &= (p[i][j] == 1);
				else ok &= (p[i][j] == 2);
			}
			else{
				ok &= (p[i][j] == 0);
			}
		}
	}
	
	if(!ok) return 0;
	
	for(int i = 0; i < n; i++){
		if(dsu2.find(i) != i) continue;
		vector<ll> v;
		for(int j = 0; j < n; j++){
			if(dsu2.find(j) == i) v.push_back(j);
		}
		for(int j = 0; j < (int)v.size() - 1; j++){
			answer[v[j]][v[j + 1]] = answer[v[j + 1]][v[j]] = 1;
		}
		if(v.size() > 1){
			answer[v[0]][v.back()] = answer[v.back()][v[0]] = 1;
		}
	}	

	for(int i = 0; i < n; i++){
		if(dsu1.find(i) != i) continue;
		vector<ll> v;
		for(int j = 0; j < n; j++){
			if(dsu1.find(j) == i && i != j) v.push_back(j);
		}
		for(int j = 0; j < (int)v.size(); j++){
			answer[v[j]][i] = answer[i][v[j]] = 1;
		}
	}	
	
	build(answer);
	return 1;
}

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