Submission #1161433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161433		Alfraganus	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	1103 ms	2162688 KiB

supertrees

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

using namespace std;

struct DSU {

	int size = 1;
	vector<int> par, sz;

	DSU (int n){
		par.resize(n);
		sz.resize(n);
		for(int i = 0; i < n; i ++)
			par[i] = i - 1, sz[i] = 1;
	}

	void merge(int a, int b){
		a = find(a);
		b = find(b);

		if(a == b)
			return;
		
		if(sz[a] < sz[b])
			swap(a, b);

		par[b] = a;
		sz[a] += sz[b];
	}

	int find(int n){
		if(par[n] != n)
			return par[n] = find(n);
		return par[n];
	}

};

int construct(vector<vector<int>> p) {
	int n = (int)p.size();
	DSU d(n);
	vector<vector<int>> ans(n, vector<int> (n));
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			if(p[i][j] == 1 and d.find(i) != d.find(j))
				d.merge(i, j), ans[i][j] = ans[j][i] = 1;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			if(p[i][j] == 0 and d.find(i) == d.find(j))
				return 0;
	build(ans);
	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