Submission #417496

#	Time	Username	Problem	Language	Result	Execution time	Memory
417496		Chaska	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	257 ms	27972 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n ;
int a[N][N];
int dad[N];
bool vs[N];
bool act[N];
struct UnionFind {
	int ran;
	int da;
};
UnionFind uf[N];
vector<std::vector<int>> answer;
vector<int> g[N];
int bus(int u)
{
	if (uf[u].da != u) uf[u].da = bus(uf[u].da);
	return uf[u].da;
}
void unir(int u,int v)
{
	u = bus(u);
	v = bus(v);
	if (u != v) {
		if (uf[u].ran > uf[v].ran) uf[v].da = u;
		else if (uf[u].ran < uf[v].ran) uf[u].da = v;
		else {
			uf[u].ran++;
			uf[v].da = u;
		}
	}
	return;
}
int construct(std::vector<std::vector<int>> _p) {
	n = _p.size();
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = _p[i][j];
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] > 2) 
		return 0;
	for (int i=0;i<n;i++) {
		uf[i].ran = 0;
		uf[i].da = i;
	}
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]>0) unir(i,j);
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j] == 0) if (bus(i) == bus(j)) {
		return 0;
	}
	for (int i=0;i<n;i++) g[bus(i)].push_back(i);
	for (int i=0;i<n;i++) {
		for (int j=0;j<(int)g[i].size();j++) act[g[i][j]] = true;
		for (int j=0;j<(int)g[i].size();j++) {
			int x = g[i][j];
			for (int k=0;k<(int)g[i].size() && act[x];k++) {
				int y = g[i][k];
				if (x != y) {
					if (a[x][y] == 1) {
						if (act[y]) {
							act[x] = false;
							dad[x] = y;
						} else if (dad[y] != x) {
							dad[x] = dad[y];
							act[x] = false;
						}
					}
				}
			}
		}
		vector<int> gg;

		for (int j=0;j<(int)g[i].size();j++) if (act[g[i][j]]) gg.push_back(g[i][j]);
		for (int j=1;j<(int)gg.size();j++) {
			answer[gg[j]][gg[j-1]] = answer[gg[j-1]][gg[j]] = 1;
		}
		int  pp = gg.size();
		if (pp>1) answer[gg[0]][gg[pp-1]] = answer[gg[pp-1]][gg[0]] = 1;
		for (int j=0;j<(int)g[i].size();j++) if (!act[g[i][j]]) {
			int x = g[i][j];
			answer[x][dad[x]] = answer[dad[x]][x] = 1;
		}
	}
	build(answer);
	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