Submission #1248980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248980		Nurislam	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	121 ms	22144 KiB

supertrees

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

using namespace std;


struct dsu {
	vector<int> p, sz;
	
	dsu(int n) {
		p.resize(n);
		iota(p.begin(), p.end(), 0);
		sz.resize(n, 1);
	};
	
	int f (int x) {
		return (p[x] == x? x: p[x] = f(p[x]));
	};
	
	int unin(int x, int y) {
		x = f(x); y = f(y);
		if(x == y) return 0;
		if(sz[x] < sz[y]) swap(x, y);
		
		sz[y] += sz[y];
		p[y] = x;
		
		return 1;
	};
	
};

int construct(vector<vector<int>> p) {
	
	int n = p.size();
	vector<vector<int>> ans(n, vector<int> (n));
	
	dsu t(n);
	
	auto ad = [&](int x, int y) {
		ans[x][y] = 1;
		ans[y][x] = 1;
		t.unin(x, y);
	};
	
	
	for(int i = 0; i < n; i ++ ) {
		for(int j = 0; j < n; j ++ ) {
			if(p[i][j] == 1 && t.unin(i, j)) ad(i, j);
		};
	};
	
	for(int i = 0; i < n; i ++ ) {
		for(int j = 0; j < n; j ++ ) {
			if(t.f(i) == t.f(j) && p[i][j] == 0) return 0;
		};
	};
	
	//{vector<int> ch(n);
		//for(int i = 0; i < n; i ++ ) {
			//if(ch[i])continue;
			//vector<int> vs(n);
		//};
	//};
	
	
	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