Submission #771511

#	Time	Username	Problem	Language	Result	Execution time	Memory
771511		khshg	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	170 ms	23212 KiB

supertrees

#include"supertrees.h"
#include<bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> P, ans, D;
vector<int> par;

int parent(int x) {
	return (par[x] == x ? x : par[x] = parent(par[x]));
}

int unite(int x, int y) {
	x = parent(x);
	y = parent(y);
	if(x == y) return 1;
	if((int)D[x].size() < (int)D[y].size()) swap(x, y);
	for(auto& u : D[x]) for(auto& v : D[y]) {
		if(!P[u][v]) return 0;
	}
	for(auto& u : D[y]) D[x].emplace_back(u);
	par[y] = x;
	return 1;
}

int construct(vector<vector<int>> _p) {
	swap(P, _p);
	N = (int)P.size();
	D.resize(N);
	par.resize(N); iota(begin(par), end(par), 0);
	for(int i = 0; i < N; ++i) D[i].push_back(i);
	for(int i = 0; i < N; ++i) {
		for(int j = i + 1; j < N; ++j) {
			if(P[i][j]) {
				if(!unite(i, j)) {
					return 0;
				}
			}
		}
	}
	vector<int> comps;
	{
		set<int> s;
		for(int i = 0; i < N; ++i) {
			s.insert(parent(i));
		}
		comps = vector<int>(begin(s), end(s));
	}
	ans = vector<vector<int>>(N, vector<int>(N, 0));
	for(auto& u : comps) {
		for(int i = 1; i < (int)D[u].size(); ++i) {
			ans[D[u][i]][D[u][i - 1]] = 1;
			ans[D[u][i - 1]][D[u][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