Submission #1288280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288280		harryleee	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	99 ms	22180 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1e3;

struct DSU{
	vector<int> par, sz, trace;
	int cnt;
	inline DSU(int n){
		par.resize(n);
		sz.resize(n, 1);
		for (int i = 0; i < n; ++i) par[i] = i;
		trace.resize(n, -1);
		cnt = -1;
	}
	inline int find(int x){
		return (par[x] == x) ? x : (par[x] = find(par[x]));
	}
	inline void merge(int x, int y){
		int u = find(x), v = find(y);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
		return;
	}
	inline int order(int x){
		int u = find(x);
		if (trace[u] == -1)
			trace[u] = ++cnt;
		return trace[u];
	}
};

int construct(vector<vector<int>> p){
	int n = p[0].size();
	vector<vector<int>> vec(n);
	vector<vector<int>> a (n, vector<int> (n, 0));
	vector<bool> circle(n, false);
	DSU dsu(n);

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (p[i][j] != 0) dsu.merge(i, j);
		}
	}

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
				return 0;
		}
	}

	for (int i = 0; i < n; ++i)
		vec[dsu.order(i)].push_back(i);
	int cnt = dsu.cnt;

	for (int k = 0; k <= cnt; ++k){
		vector<int>& v = vec[k];
		vector<int> in;
		for (int i : v){
			for (int j : v)
				if (p[i][j] == 2) circle[i] = true;
			if (circle[i]) for (int j : v)
				if (p[i][j] == 1 && circle[j]) circle[i] = false;
			if (circle[i]) in.push_back(i);
		}
		if (in.empty()){
			for (int i = 0; i < v.size() - 1; ++i)
				a[v[i]][v[i + 1]] = a[v[i + 1]][v[i]] = true;
		}
		else{
			for (int i = 0; i < in.size() - 1; ++i)
				a[in[i]][in[i + 1]] = a[in[i + 1]][in[i]] = true;
			a[in.back()][in[0]] = a[in[0]][in.back()] = true;
			for (int i : in){
				int cur = i;
				for (int j : v){
					if (p[i][j] == 1){
						a[cur][j] = a[j][cur] = 1;
						cur = j;
					}
				}
			}
		}
	}

	build(a);
	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