Submission #795872

#	Time	Username	Problem	Language	Result	Execution time	Memory
795872		hgmhc	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	185 ms	24140 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ii = pair<int,int>;

const int N = 1003;
int n;
vector<vector<int>> adj;

struct disjoint_set {
	int p[N];
	disjoint_set(){ iota(p,p+N,0); }
	int find(int x){
		if (x==p[x]) return x;
		return p[x]=find(p[x]);
	}
	bool same(int a, int b){ return find(a)==find(b); }
	void merge(int a, int b) {
		a = find(a), b = find(b);
		assert(a!=b);
		p[a]=b;
	}
} ds, DS;

bool found3(vector<vector<int>> &p) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 3) return true;
		}
	}
	return false;
}

vector<int> roots;

void connect_ones(vector<vector<int>> &p) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) if (p[ds.find(i)][ds.find(j)] == 1) {
			if (not ds.same(i,j)) {
				adj[ds.find(i)][ds.find(j)] =
				adj[ds.find(j)][ds.find(i)] = 1;
				ds.merge(i,j);
			}
		}
	}
}

bool doit(vector<vector<int>> &p) {
	for (int i = 0; i < n; ++i) roots.push_back(ds.find(i));
	sort(all(roots)), roots.erase(unique(all(roots)),end(roots));
	for (auto r1 : roots) for (auto r2 : roots) if (p[r1][r2] == 2) {
		if (not DS.same(r1,r2)) DS.merge(r1,r2);
	}
	vector<vector<int>> comp(n);
	for (auto r : roots) comp[DS.find(r)].push_back(r);
	for (auto &c : comp) {
		if (siz(c) < 2) continue;
		if (siz(c) == 2) return false;
		for (int j = 0; j < siz(c); ++j) {
			adj[c[j]][c[(j+1)%siz(c)]] = 1;
			adj[c[(j+1)%siz(c)]][c[j]] = 1;
		}
	}
	return true;
}

int construct(vector<vector<int>> p) {
	n = p.size(), adj.resize(n,vector<int>(n));
	if (found3(p)) return 0;
	connect_ones(p);
	if (!doit(p)) return 0;
	
	for (int i = 0; i < n; ++i) {
		adj[i][i] = 0;
		for (int j = 0; j < n; ++j) if (i != j) {
			if (p[i][j] == 0) {
				if (ds.same(i,j)) return 0;
				if (DS.same(ds.find(i),ds.find(j))) return 0;
			} else if (p[i][j] == 1) {
				if (not ds.same(i,j)) return 0;
			} else if (p[i][j] == 2) {
				if (ds.same(i,j)) return 0;
				if (not DS.same(ds.find(i),ds.find(j))) return 0;
			} else assert(0);
		}
	}
	
	build(adj);
	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