Submission #1255038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255038		mingga	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	238 ms	22192 KiB

supertrees

// Author: caption_mingle
#include "bits/stdc++.h"
#include "supertrees.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;

struct DSU {
	int n;
	vector<int> par,sz;
	DSU() {}
	DSU(int n) : n(n) {
		par.resize(n, 0);
		sz.resize(n, 1);
		for(int i = 1; i < n; i++) par[i] = i;
	}
	int find(int u) {
		return u == par[u] ? u : par[u] = find(par[u]);
	}
	void join(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);
		sz[u] += sz[v];
		par[v] = u;
	}
};

int construct(vector<vector<int>> p) {
	int n = sz(p);
	vector<vector<int>> ans(n, vector<int>(n, 0));
	DSU d(n);
	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]) d.join(i, j);
		}
	}
	vector<vector<int>> gp(n);
	for(int i = 0; i < n; i++) {
		gp[d.find(i)].pb(i);
		for(int j = 1; j < n; j++) {
			if(d.find(i) == d.find(j) and p[i][j] == 0) return 0;
		}
	}
	for(int i = 0; i < n; i++) {
		if(sz(gp[i]) <= 1) continue;
		bool check1 = 1;
		if(sz(gp[i]) >= 3) {
			for(int j = 0; j < sz(gp[i]); j++) {
				int u = gp[i][j];
				for(int k = j + 1; k < sz(gp[i]); k++) {
					int v = gp[i][k];
					for(int t = k + 1; t < sz(gp[i]); t++) {
						int w = gp[i][t];
						if(p[u][v] * p[v][w] * p[u][w] == 2) return 0;
						if(p[u][v] * p[v][w] * p[u][w] != 1) check1 = 0;
					}
				}
			}
		} else if(p[gp[i][0]][gp[i][1]] == 2) return 0;
		if(check1) {
			for(int j = 1; j < sz(gp[i]); j++) {
				ans[gp[i][j]][gp[i][j - 1]] = 1;
				ans[gp[i][j - 1]][gp[i][j]] = 1;
			}
			continue;
		}
		int st = -1;
		vector<bool> mark(n, 0);
		for(int j = 0; j < sz(gp[i]); j++) {
			int u = gp[i][j];
			for(int k = j + 1; k < sz(gp[i]); k++) {
				int v = gp[i][k];
				if(p[u][v] == 2) {
					st = u;
					break;
				}
			}
			if(st != -1) break;
		}
		vector<int> circle;
		circle.pb(st);
		mark[st] = 1;
		while(1) {
			bool ok = 0;
			int cur = circle.back();
			for(int j = 0; j < sz(gp[i]); j++) {
				int u = gp[i][j];
				if(mark[u]) continue;
				ok = 1;
				for(int v : circle) {
					if(p[u][v] == 1) {
						ok = 0;
						break;
					}
				}
				if(ok) {
					circle.pb(u), mark[u] = 1;
					break;
				}
			}
			if(!ok) break;
		}
		if(sz(circle) < 3) return 0;
		ans[circle[0]][circle.back()] = 1;
		ans[circle.back()][circle[0]] = 1;

		for(int j = 0; j < sz(circle); j++) {
			int u = circle[j];
			if(j > 0) {
				ans[u][circle[j - 1]] = 1;
				ans[circle[j - 1]][u] = 1;
			}
			for(int k = 0; k < sz(gp[i]); k++) {
				int v = gp[i][k];
				if(mark[v]) continue;
				if(p[u][v] == 1) {
					ans[u][v] = 1;
					ans[v][u] = 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