Submission #771570

#	Time	Username	Problem	Language	Result	Execution time	Memory
771570		khshg	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	184 ms	22116 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] != 1) 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] == 1) {
				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 = 0; i < (int)D[u].size(); ++i) {
			if(D[u][i] == u) swap(D[u][i], D[u][0]);
		}
		for(int i = 1; i < (int)D[u].size(); ++i) {
			ans[u][D[u][i]] = 1;
			ans[D[u][i]][u] = 1;
		}
	}
	vector<bool> did(N);
	for(int i = 0; i < N; ++i) {
		if(did[parent(i)]) continue;
		did[parent(i)] = 1;
		vector<int> ids = {i};
		for(int j = i + 1; j < N; ++j) {
			if(P[i][j] == 2) {
				ids.push_back(j);
			}
		}
		if((int)ids.size() == 1) continue;
		{
			set<int> s;
			for(auto& u : ids) {
				s.insert(parent(u));
			}
			ids = vector<int>(begin(s), end(s));
		}
		ans[ids[0]][ids.back()] = 1;
		ans[ids.back()][ids[0]] = 1;
		for(int i = 1; i < (int)ids.size(); ++i) {
			did[ids[i]] = 1;
			ans[ids[i]][ids[i - 1]] = 1;
			ans[ids[i - 1]][ids[i]] = 1;
		}
	}
	build(ans);
	return 1;
}

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