Submission #873390

#	Time	Username	Problem	Language	Result	Execution time	Memory
873390		bobbilyking	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	183 ms	22352 KiB

supertrees

#include "supertrees.h"
using namespace std;
#include <bits/stdc++.h>
using ll=long long;
 
#define F(i, l, r) for (ll i = (l); i < ll(r); ++i)
bool vis[1010];
vector<ll> comp;
 
struct info {
	vector<ll> twos;
	vector<vector<ll>> ones;
};
 
vector<info> glob;
 
void dfs(ll i, vector<vector<int>>& p) {
	if (vis[i]) return;
	vis[i] = 1;
	comp.push_back(i);
	F(j, 0, p.size()) if (p[i][j]) dfs(j, p);
}
 
ll dsu[1010];
vector<ll> st[1010];
ll find(ll i) {
	return dsu[i] == i ? i: dsu[i] = find(dsu[i]);
}
 
 
bool my_build(std::vector<std::vector<int>>& b) {
	for (auto &[twos, ones]: glob) {
		bool flag = false;
		if (!twos.size()) {
			// if it's just one one, then we can get away with not doing shit
			// else, if it's two ones, we can't do it
			// else, we gotta make a cycle
			if (ones.size() == 1) flag = false;
			else if (ones.size() == 2) return false;
			else flag = true;
		} else {
			// we have a cycle, everyones gotta contribute
			flag = 1;
		}
		// for (auto x: twos) cout << x << " "; cout << endl;
		// cout << "-----\n";
		// for (auto v: ones) {
		// 	for (auto x: v)  cout << x << " "; cout << endl;
		// }
		// cout << "============\n";

		for (const auto &y: ones) {
			if (flag) twos.push_back(y[0]); // then we actually neeed this shit
			for (ll i = 0; i + 1 < ll(y.size()); ++i) b[y[i]][y[i+1]] = b[y[i+1]][y[i]] = 1;
		}
		if (twos.size() != 0 and twos.size() < 3) return false; // cant have a cycle with less than 3 nodes bruh
		F(i, 0, twos.size()) {
			ll nidx = (i+1)%twos.size();
			b[twos[i]][twos[nidx]] = b[twos[nidx]][twos[i]] = 1;
		}
	}
	return 1;
}
 
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
 
	for (auto &x: p) for (auto y: x) if (y==3) return 0;
	F(i, 0, n) {
		dsu[i] = i;
		st[i] = {i};
	}
 
	F(i, 0, n) if (!vis[i]) {
		comp.clear();
		dfs(i, p);
		if (comp.size() == 1) continue; // empty live my life yo
		info cur;
 
		for (auto idx: comp) {
			ll ign = 0;
			for (auto x: comp) if (x-idx) {
				if (!p[idx][x]) return false; // everything within component is connected
				if (p[idx][x] == 1) {
					ll u = find(idx), v = find(x);
					if (u-v) {	
						if (st[u].size() < st[v].size()) swap(u, v);
						dsu[v] = u;
						st[u].insert(st[u].end(), st[v].begin(), st[v].end());
					}
				} else ign++;
			}
			if (ign + 1 == ll(comp.size())) cur.twos.push_back(idx); // all twos
		}
 
		set<ll> ivis;
		for (auto idx: comp) if (st[find(idx)].size() > 1) ivis.insert(find(idx));
		for (auto idx: ivis) {
			for (auto y: st[idx]) for (auto z: st[idx]) if (p[y][z] != 1) return false;
			cur.ones.push_back(st[idx]);
		}
 
		glob.push_back(cur);
	}	
 
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	if (!my_build(answer)) return false;
 
	build(answer);
	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