Submission #305011

#	Time	Username	Problem	Language	Result	Execution time	Memory
305011		srvlt	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	261 ms	26232 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
#define cps2(x, y) sort(all(x), y), (x).erase(unique(all(x)), end(x))
#define mem(x, y) memset(& x, y, sizeof(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1003;
int n, used[n0], g2[n0][n0];
vector <int> comp;
bitset <n0> g[n0], b;

void dfs(int v) {
	comp.pb(v);
	used[v] = 1;
	for (int to = 0; to < n; to++) {
		if (!g[v][to] || used[to]) continue;
		dfs(to);
	}
}

int construct(vector<vector<int>> p) {
	n = p.size();
	int type = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j]) g[i][j] = 1;
			if (p[i][j] == 2) type = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			comp.clear();
			dfs(i);
			b = g[comp[0]];
			for (int j : comp)
				if (b != g[j]) return 0;
			if (!type) {
				for (int j = 1; j < SZ(comp); j++)
					g2[comp[0]][comp[j]] = 1;
			}	else {
				if (SZ(comp) == 2) return 0;
				for (int j = 0; j < SZ(comp); j++)
					g2[comp[j]][comp[(j + 1) % SZ(comp)]] = 1;
			}
		}
	}
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		for (int j = 0; j < n; j++)
			if (g2[i][j] || g2[j][i]) row[j] = 1;
		answer.push_back(row);
	}
	build(answer);
	return 1;
}

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