Submission #1248998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248998		Nurislam	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	139 ms	22180 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[x] += 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);
		};
	};
	vector<int> p2(n);
	{vector<int> ch(n);
		for(int i = 0; i < n; i ++ ) {
			if(ch[t.f(i)])continue;
			
			vector<int> vs(n), al;
			queue<int> q;
			for(int j = 0; j < n; j ++ ) {
				if(t.f(i) != t.f(j) && p[i][j] == 2) {
					q.push(t.f(i));
					vs[t.f(i)] = 1;
					break;
				};
			};
			
			while(q.size()) {
				auto ps = q.front();
				q.pop();
				al.push_back(ps);
				ch[ps] = 1;
				
				for(int j = 0; j < n; j ++ ) {
					if(p[ps][j] == 3) return  0;
					if(vs[t.f(j)]) continue;
					if(ps != t.f(j) && p[ps][j] == 2) {
						q.push(t.f(j));
						vs[t.f(j)] = 1;
					};
				};
			};
			
			if(al.size() > 1 && al.size() <= 2) return 0;
			
			for(int j = 0; j < (int)al.size(); j ++ ) ad(al[j], al[(j+1) %al.size()]);
			if(al.size()) p2[t.f(i)] = 1;
		};
	};
	{vector<int> ch(n);
		for(int i = 0; i < n; i ++ ) {
			if(ch[t.f(i)])continue;
			
			vector<int> vs(n), al;
			queue<int> q;
			for(int j = 0; j < n; j ++ ) {
				if(t.f(i) != t.f(j) && p[i][j] == 3) {
					q.push(t.f(i));
					vs[t.f(i)] = 1;
					break;
				};
			};
			
			while(q.size()) {
				auto ps = q.front();
				if(p2[ps] == 1) return 0;
				q.pop();
				al.push_back(ps);
				ch[ps] = 1;
				
				for(int j = 0; j < n; j ++ ) {
					if(vs[t.f(j)]) continue;
					if(ps != t.f(j) && p[ps][j] == 3) {
						q.push(t.f(j));
						vs[t.f(j)] = 1;
					};
				};
			};
			
			if(al.size() > 1 && al.size() <= 3) return 0;
			if(al.size() == 0)continue;
			for(int j = 0; j < (int)al.size(); j ++ ) ad(al[j], al[(j+1) %al.size()]);
			ad(al[0], al[2]);
			p2[t.f(i)] = 2;
		};
	};
	
	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;
			if(p[i][j] == 2 && (p2[t.f(i)] != 1 || p2[t.f(j)] != 1)) return 0;
			if(p[i][j] == 3 && (p2[t.f(i)] != 2 || p2[t.f(j)] != 2)) return 0;
		};
	};
	for(int i = 0; i < n; i ++ ) {
		if(p2[t.f(i)] == 1) 
			for(int j = 0; j < n; j ++ ) 
				if(p[i][j] == 3) return 0;
	};
	
	build(ans);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4