Submission #300687

#	Time	Username	Problem	Language	Result	Execution time	Memory
300687		Temmie	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	327 ms	26360 KiB

supertrees

#include <bits/stdc++.h>

void build(std::vector <std::vector <int>> b);

void ff1(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
	if (vis[node]) return;
	vis[node] = true;
	col.back().push_back(node);
	for (int i = 0; i < n; i++) {
		if (p[node][i] == 1) {
			ff1(i, n, p, col, vis);
		}
	}
}

void ff2(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
	if (vis[node]) return;
	vis[node] = true;
	col.back().push_back(node);
	for (int i = 0; i < n; i++) {
		if (p[node][i] == 2) {
			ff2(i, n, p, col, vis);
		}
	}
}

void dfs(int node, int n, std::vector <bool>& vis, std::vector <int>& cnt, std::vector <std::vector <int>>& g) {
	if (vis[node]) return;
	vis[node] = true;
	cnt[node]++;
	for (int x : g[node]) {
		dfs(x, n, vis, cnt, g);
	}
	vis[node] = false;
}

int construct(std::vector <std::vector <int>> p) {
	
	std::vector <std::vector <int>> ep(p);
	int n = p.size();
	std::vector <std::vector <int>> ocol;
	for (int i = 0; i < n; i++) {
		static std::vector <bool> vis(n, false);
		if (vis[i]) continue;
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 1) {
				ocol.push_back({ });
				ff1(i, n, p, ocol, vis);
				break;
			}
		}
	}
	for (auto& v : ocol) {
		for (size_t i = 1; i < v.size(); i++) {
			for (int j = 0; j < n; j++) {
				p[v[i]][j] = p[j][v[i]] = 0;
			}
			p[v[i]][v[i]] = 1;
		}
	}
	std::vector <std::vector <int>> tcol;
	for (int i = 0; i < n; i++) {
		static std::vector <bool> vis(n, false);
		if (vis[i]) continue;
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 2) {
				tcol.push_back({ });
				ff2(i, n, p, tcol, vis);
				break;
			}
		}
	}
	std::vector <std::vector <int>> ans(n, std::vector <int> (n, 0));
	for (auto& v : ocol) {
		for (size_t i = 0; i < v.size() - 1; i++) {
			ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
		}
	}
	for (auto& v : tcol) {
		for (size_t i = 0; i < v.size() - 1; i++) {
			ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
		}
		ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1;
	}
	std::vector <std::vector <int>> adj(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans[i][j]) adj[i].push_back(j);
		}
	}
	for (int i = 0; i < n; i++) {
		std::vector <bool> vis(n, false);
		std::vector <int> cnt(n, 0);
		dfs(i, n, vis, cnt, adj);
		for (int j = 0; j < n; j++) {
			if (ep[i][j] != cnt[j]) return 0;
		}
	}
	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