Submission #771589

#	Time	Username	Problem	Language	Result	Execution time	Memory
771589		khshg	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	222 ms	26688 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;
				}
			} else if(P[i][j] == 3) 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));
	}
	vector<vector<int>> twos(N);
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			if(P[i][j] == 2) {
				twos[i].push_back(j);
			}
		}
	}
	ans = vector<vector<int>>(N, vector<int>(N, 0));
	map<vector<int>, vector<int>> cycles;
	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) {
			if(twos[u] != twos[D[u][i]]) return 0;
			ans[u][D[u][i]] = 1;
			ans[D[u][i]][u] = 1;
		}
		twos[u].push_back(u);
		{
			set<int> s;
			for(auto& v : twos[u]) {
				s.insert(parent(v));
			}
			twos[u] = vector<int>(begin(s), end(s));
		}
		cycles[twos[u]].emplace_back(u);
	}
	for(auto& u : cycles) {
		if(u.first != u.second) return 0;
		if(u.first.size() == 2) return 0;
		if(u.first.size() == 1) continue;
		ans[u.first[0]][u.first.back()] = 1;
		ans[u.first.back()][u.first[0]] = 1;
		for(int i = 1; i < (int)u.first.size(); ++i) {
			ans[u.first[i]][u.first[i - 1]] = 1;
			ans[u.first[i - 1]][u.first[i]] = 1;
		}
	}
	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: 4 / 4