Submission #424916

#	Time	Username	Problem	Language	Result	Execution time	Memory
424916		Mlxa	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	296 ms	31912 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "supertrees.h"

namespace my {

const int N = 1010;
int n, g[N][N], res[N][N];

void edge(int v, int u) {
	res[v][u] = true;
	res[u][v] = true;
}

vector<int> get_comp(int v, int msk) {
	static int lst[N], timer = 0;
	++timer;
	lst[v] = timer;
	queue<int> q;
	vector<int> ret;
	q.push(v);
	while (q.size()) {
		v = q.front(); q.pop();
		ret.push_back(v);
		for (int u = 0; u < n; ++u) {
			if (lst[u] == timer) {
				continue;
			}
			if ((msk >> g[v][u]) & 1) {
				lst[u] = timer;
				q.push(u);
			}
		}
	}
	return ret;
}

bool u1[N], u12[N];
}

int construct(vector<vector<int>> _g) {
	using namespace my;
	n = (int)_g.size();
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = _g[i][j];
			if (g[i][j] == 3) {
				return 0;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (u12[i]) {
			continue;
		}
		vector<int> c12 = get_comp(i, (1 << 1) | (1 << 2));
		// cout << "! " << c12.size() << endl;
		vector<int> cycle;
		for (int v : c12) {
			u12[v] = true;
			if (u1[v]) {
				continue;
			}
			vector<int> c1 = get_comp(v, 1 << 1);
			// cout << "? " << c1.size() << " " << c1[0] << endl;
			for (int u : c1) {
				for (int uu : c1) {
					if (g[u][uu] != 1) {
						return 0;
					}
				}
				u1[u] = true;
			}
			for (int u : c1) {
				for (int uu : c12) {
					if (u1[uu]) {
						continue;
					}
					if (g[u][uu] != 2) {
						return 0;
					}
				}
			}
			for (int idx = 0; idx + 1 < (int)c1.size(); ++idx) {
				edge(c1[idx], c1[idx + 1]);
			}
			cycle.push_back(c1.front());
		}
		if (cycle.size() == 1) {
			continue;
		}
		for (int idx = 0; idx < (int)cycle.size(); ++idx) {
			edge(cycle[idx], cycle[(idx + 1) % cycle.size()]);
		}
	}
	vector<vector<int>> answer;
	for (int i = 0; i < n; ++i) {
		answer.push_back(vector<int>(res[i], res[i] + n));
	}
	build(answer);
	return 1;
}

#ifdef LC
#include "grader.cpp"
#endif

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4