Submission #1115710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115710		Pekiban	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	161 ms	28040 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 1001;
struct dsu {
	int p[N], sz[N];
	void init(int n) {
		fill(sz, sz+n, 1);
		iota(p, p+n, 0);
	}
	int get(int u) {
		if (u == p[u])	return u;
		return p[u] = get(p[u]);
	}
	bool unite(int u, int v) {
		u = get(u), v = get(v);
		if (u == v)	return 0;
		if (sz[u] < sz[v])	swap(u, v);
		sz[u] += sz[v];
		p[v] = u;
		return 1;
	}
} D;
bool vis[N];
int n;
vector<int> E;
vector<vector<int>> p;
void dfs(int s) {
	vis[s] = 1;
	E.pb(s);
	for (int i = 0; i < n; ++i) {
		if (p[s][D.get(i)] == 2 && !vis[D.get(i)])	dfs(D.get(i));
	}
}
int construct(vector<vector<int>> P) {
	p = P; n = p.size();
	D.init(n);
	vector<vector<int>> A(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 1) {
				if (D.unite(i, j))	A[i][j] = A[j][i] = 1;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 3 || p[i][j] != p[D.get(i)][D.get(j)])	return 0;
		}
	}
	for (int u = 0; u < n; ++u) {
		if (!vis[D.get(u)])	{
			dfs(D.get(u));
			for (int i = 0; i < (int)E.size(); ++i) {
				for (int j = 0; j < i; ++j) {
					if (p[E[i]][E[j]] != 2)	return 0;
				}
			}
			if (E.size() == 1) {
				E.clear();
				continue;
			}
			if (E.size() == 2)	return 0;
			for (int i = 0; i+1 < (int)E.size(); ++i)	A[E[i]][E[i+1]] = A[E[i+1]][E[i]] = 1;
			A[E.back()][E[0]] = A[E[0]][E.back()] = 1;
			E.clear();
		}
	}
	build(A);
	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