Submission #1039659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039659		DorostWef	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	137 ms	32336 KiB

supertrees

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

using namespace std;
const int N = 1032;
vector <int> g1[N], g2[N];
int r1[N], r2[N];
bool vis[N];
vector <int> v[N];

void dfs1 (int v) {
	vis[v] = true;
	for (int u : g1[v]) {
		if (!vis[u]) {
			r1[u] = r1[v];
			dfs1 (u);
		}
	}
}

void dfs2 (int v) {
	vis[v] = true;
	for (int u : g2[v]) {
		if (!vis[u]) {
			r2[u] = r2[v];
			dfs2 (u);
		}
	}
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 1) {
				g1[i].push_back(j);
				g1[j].push_back(i);
			} 
			if (p[i][j] >= 1) {
				g2[i].push_back(j);
				g2[j].push_back(i);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			r1[i] = i;
			dfs1(i);
		}
	}
	for (int i = 0; i < n; i++) 
		vis[i] = false;
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			r2[i] = i;
			dfs2(i);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int w;
			if (r2[i] != r2[j]) {
				w = 0;
			} else if (r1[i] == r1[j]) {
				w = 1;
			} else {
				w = 2;
			}
			if (p[i][j] != w)
				return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		if (r1[i] != i) {
			ans[i][r1[i]] = 1;
			ans[r1[i]][i] = 1;
		} else {
			v[r2[i]].push_back(i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (v[i].size() == 2)
			return 0;
		if (v[i].size() <= 1)
			continue;
		int sz = (int)v[i].size();
		for (int j = 0; j < sz; j++) {
			ans[v[i][j]][v[i][(j + 1) % sz]] = true;
			ans[v[i][(j + 1) % sz]][v[i][j]] = true;
		}
	}
	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