Submission #412633

#	Time	Username	Problem	Language	Result	Execution time	Memory
412633		dynam1c	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	290 ms	22084 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define endl "\n"
typedef long long ll;

struct DSU {
	int n;
	vector<int> link, sz;
	DSU(int n) : n(n), link(n), sz(n, 1) {
		iota(all(link), 0);
	}
	int find(int x) {
		return link[x] == x ? x : link[x] = find(link[x]);
	}
	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return false;
		if (sz[x] < sz[y]) swap(x, y);
		link[y] = x;
		sz[x] += sz[y];
		return true;
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n, vector<int>(n));
	DSU dsu1(n), dsu2(n);
	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			if (p[i][j] == 1)
				if (dsu1.unite(i, j))
					ans[i][j] = 1, ans[j][i] = 1;
	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			if (p[i][j] == 2)
				dsu2.unite(dsu1.find(i), dsu1.find(j));
	
	for (int i = 0; i < n; i++) {
		int p = -1;
		int f = -1;
		for (int j = 0; j < n; j++)
			if (dsu2.find(j) == i) {
				if (f == -1)
					f = j;
				if (p != -1)
					ans[j][p] = 1, ans[p][j] = 1;
				p = j;
			}
		if (f != p)
			ans[f][p] = 1, ans[p][f] = 1;
	}

	for (int i = 0; i < n; i++)
		if (p[i][i] != 1)
			return 0;
	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++) {
			if (p[i][j] == 0 and (dsu1.find(i) == dsu1.find(j) or dsu2.find(dsu1.find(i)) == dsu2.find(dsu1.find(j))))
				return 0;
			if (p[i][j] == 1 and dsu1.find(i) != dsu1.find(j))
				return 0;
			if (p[i][j] == 2 and (dsu1.find(i) == dsu1.find(j) or dsu2.find(dsu1.find(i)) != dsu2.find(dsu1.find(j))))
				return 0;
			if (p[i][j] == 3)
				return 0;
		}
	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