Submission #1161792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161792		Alfraganus	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	1096 ms	320 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));
	vector<bool> used(n + 1);
	for(int i = 0; i < n; i ++){
		if(used[i])
			continue;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int cur = q.front();
			q.pop();
			if(cur == i and used[cur])
				break;
			if(used[cur] == 1)
				return 0;
			used[cur] = 1;

			for(int j = 0; j < n; j ++){
				if(p[cur][j] == 2){
					d.merge(cur, j);
					q.push(j);
					ans[cur][j] = 1;
					ans[j][cur] = 1;
					break;
				}
			}
		}
	}
	for(int i = 0; i < n; i ++){
		if(used[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){
						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;
			if(p[i][j] == 1 and d.find(i) != d.find(j)){
				d.merge(i, j);
				ans[i][j] = 1;
				ans[j][i] = 1;
			}
		}
	}
	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