Submission #1178977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178977		Pacybwoah	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	216 ms	22184 KiB

supertrees

#include "supertrees.h"
#include<vector>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
	struct DSU{
		int n;
		vector<int> dsu, sz;
		DSU(int _n){
			n = _n;
			dsu.resize(n + 1);
			sz.resize(n + 1);
			for(int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
		}
		int query(int x){
			if(x == dsu[x]) return x;
			dsu[x] = query(dsu[x]);
			return dsu[x];
		}
		void unite(int a, int b){
			a = query(a);
			b = query(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			sz[a] += sz[b];
			dsu[b] = a;
		}
	};
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n, vector<int>(n));
	DSU dsu1(n);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(p[i][j] > 0) dsu1.unite(i, j);
			if(p[i][j] == 3) return 0;
		}
	}
	vector<vector<int>> comps(n);
	for(int i = 0; i < n; i++){
		comps[dsu1.query(i)].push_back(i);
	}
	for(int pa = 0; pa < n; pa++){
		if(comps[pa].empty()) continue;
		int sz = (int)comps[pa].size();
		DSU dsu2(sz);
		for(int i = 0; i < sz; i++){
			for(int j = i + 1; j < sz; j++){
				if(p[comps[pa][i]][comps[pa][j]] == 0) return 0;
				if(p[comps[pa][i]][comps[pa][j]] == 1) dsu2.unite(i, j);
			}
		}
		vector<vector<int>> vec(sz);
		for(int i = 0; i < sz; i++) vec[dsu2.query(i)].push_back(i);
		for(int i = 0; i < sz; i++){
			for(int j = 0; j < sz; j++){
				if(dsu2.query(i) == dsu2.query(j)){
					if(p[comps[pa][i]][comps[pa][j]] != 1) return 0;
				}
				else{
					if(p[comps[pa][i]][comps[pa][j]] != 2) return 0;
				}
			}
		}
		vector<int> imp;
		for(int i = 0; i < sz; i++){
			if(i == dsu2.query(i)) imp.push_back(comps[pa][i]);
			else{
				int a = comps[pa][dsu2.query(i)], b = comps[pa][i];
				ans[a][b] = 1;
				ans[b][a] = 1;
			}
		}
		int szz = (int)imp.size();
		if(szz > 1){
			if(szz == 2) return 0;
			for(int i = 0; i < szz - 1; i++){
				ans[imp[i]][imp[i + 1]] = 1;
				ans[imp[i + 1]][imp[i]] = 1;
			} 
			ans[imp[szz - 1]][imp[0]] = 1;
			ans[imp[0]][imp[szz - 1]] = 1;
		}
	}
	build(ans);
	return 1;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g grader.cpp supertrees.cpp

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