Submission #1182924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182924		esomer	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	122 ms	22180 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct DSU {
	vector<int> v;
	void init (int n) {v.assign(n, -1);}
	int get(int x) {return v[x] < 0 ? x : v[x] = get(v[x]);}
	void unite(int x, int y) {
		x = get(x); y = get(y);
		if (x == y) return;
		if (v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
	}
	bool same (int x, int y) {return (get(x) == get(y));}
};

int construct(vector<vector<int> > p) {
	int n=p.size();
	DSU all; all.init(n);
	DSU one; one.init(n);
	vector<vector<int> > ans(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			if (p[i][j] == 3) return 0;
			if (p[i][j] != 0) all.unite(i, j);
			if (p[i][j] == 1 && !one.same(i, j)) {
				one.unite(i, j);
				ans[i][j] = 1;
				ans[j][i] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 0 && all.same(i, j)) {
				//cout << i << " " << j << endl;
				return 0;
			}
			if (p[i][j] == 2 && one.same(i, j)) return 0;
			if (p[i][j] != 0 && !all.same(i, j)) return 0;
		}
	}
	for (int leader = 0; leader < n; leader++) {
		vector<int> v;
		for (int i = 0; i < n; i++) {
			if (one.get(i) == i && all.get(i) == leader) v.push_back(i);
		}
		if ((int)v.size() > 1) {
		  if ((int)v.size()==2) return 0;
			int m = (int)v.size();
			for (int i = 0; i < m; i++) {
				int j = v[(i+1)%m];
				ans[v[i]][j] = 1;
				ans[j][v[i]] = 1;
			}
		}
	}
	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