Submission #1161770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161770		Alfraganus	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	121 ms	22152 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, 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(par[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 ++){
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int cur = q.front();
			q.pop();

			for(int j = 0; j < n; j ++){
				if(p[cur][j] == 1 and d.find(j) != d.find(cur)){
					d.merge(cur, j);
					q.push(j);
					ans[cur][j] = 1;
					ans[j][cur] = 1;
					break;
				}
			}
		}
	}
	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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4