Submission #468245

#	Time	Username	Problem	Language	Result	Execution time	Memory
468245		Soumya1	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	268 ms	24116 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct DisjointSetUnion {
	int n;
	vector<int> par;
	vector<int> sz;
	DisjointSetUnion(int n) {
		par.resize(n);
		sz.assign(n, 1);
		iota(par.begin(), par.end(), 0);
	}
	int find(int x) {
		return par[x] = (x == par[x] ? x : find(par[x]));
	}
	void unite(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
	}
	bool same(int u, int v) {
		return (find(u) == find(v));
	}
};
int construct(vector<vector<int>> p) {
	int n = p.size();
	bool bad = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			bad |= (p[i][j] == 3);
		}
	}
	if (bad) return 0;
	vector<vector<int>> b(n, vector<int> (n, 0));
	DisjointSetUnion dsu(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 1) {
				dsu.unite(i, j);
			}
		}
	}
	vector<int> trees[n];
	vector<int> roots;
	for (int i = 0; i < n; i++) {
		if (dsu.par[i] == i) {
			vector<int> nodes;
			for (int j = 0; j < n; j++) {
				if (dsu.par[j] == i) {
					nodes.push_back(j);
				}
			}
			for (int u : nodes) {
				for (int v : nodes) {
					bad |= (p[u][v] != 1);
				}
			}
			trees[i] = nodes;
			roots.push_back(i);
			for (int j = 1; j < (int) nodes.size(); j++) b[nodes[j]][nodes[j - 1]] = b[nodes[j - 1]][nodes[j]] = 1;
		}
	}
	if (bad) return 0;
	DisjointSetUnion rot(n);
	for (int u : roots) {
		for (int v : roots) {
			if (p[u][v] == 2) {
				rot.unite(u, v);
			}
		}
	}
	for (int u : roots) {
		if (u == rot.par[u] && rot.sz[u] > 2) {
			vector<int> nodes;
			for (int v : roots) {
				if (u == rot.par[v]) {
					nodes.push_back(v);
				}
			}
			for (int i : nodes) {
				for (int j : nodes) {
					if (i == j) continue;
					for (int x : trees[i]) {
						for (int y : trees[j]) {
							bad |= (p[x][y] != 2);
						}
					}
				}
			}
			int sz = nodes.size();
			for (int i = 0; i < sz; i++) {
				b[nodes[i]][nodes[(i + 1) % sz]] = b[nodes[(i + 1) % sz]][nodes[i]] = 1;
			}
		} else if (u == rot.par[u] && rot.sz[u] == 2) {
			bad = true;
		}
	}
	if (bad) return 0;
	build(b);
	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