Submission #1162338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162338		Alfraganus	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	125 ms	22160 KiB

supertrees

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

using namespace std;

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

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;
		vector<int> nodes;
		int cur = i, sz = 1;
		nodes.push_back(i);
		while(sz){
			sz --;
			used[cur] = 1;
			for(int j = 0; j < n; j ++){
				if(p[cur][j] == 2 and !used[j]){
					bool flag = 1;
					for(auto y : nodes){
						if(p[j][y] != 2){
							flag = 0;
							break;
						}
					}
					if(flag){
						nodes.push_back(j);
						d.merge(cur, j);
						ans[cur][j] = 1;
						ans[j][cur] = 1;
						cur = j;
						sz ++;
						break;
					}
				}
			}
		}
		if(nodes.size() == 1)
			continue;
		if(p[nodes.front()][nodes.back()] != 2)
			return 0;
		d.merge(nodes.front(), nodes.back());
		ans[nodes.front()][nodes.back()] = 1;
		ans[nodes.back()][nodes.front()] = 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;
			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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4