Submission #1225190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225190		Nonoze	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	143 ms	22244 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se secod
#define sz(x) (int)x.size()
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back

using namespace std;

int n;
vector<int> par, sz;

int getpar(int x) {
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}

bool same(int a, int b) {
	return getpar(a)==getpar(b);
}

bool unite(int a, int b) {
	a=getpar(a), b=getpar(b);
	if (a==b) return 1;
	if (sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b], par[b]=a;
	return 1;
}

int construct(vector<vector<int>> base) {
	n = sz(base);
	par.resize(n), sz.resize(n, 1); iota(all(par), 0);
	vector<vector<int>> answer(n, vector<int>(n, 0));
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (base[i][j] && !unite(i, j)) return 0;
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (!base[i][j] && same(i, j)) return 0;
		}
	}
	vector<vector<int>> vec(n);
	for (int i=0; i<n; i++) {
		vec[getpar(i)].pb(i);
	}
	for (auto compo: vec) if (sz(compo)>1) {
		int m=sz(compo);
		vector<vector<int>> p(m, vector<int>(m));
		for (int i=0; i<m; i++) {
			for (int j=0; j<m; j++) {
				p[i][j]=base[compo[i]][compo[j]];
			}
		}
		vector<bool> used1(m, 0);
		for (int i=0; i<m; i++) if (!used1[i]) {
			vector<int> vec;
			for (int j=i; j<m; j++) {
				if (p[i][j]==1) vec.pb(j);
			}
			if (sz(vec)>1) {
				for (auto &u: vec) used1[u]=1;
				for (int j=1; j<sz(vec); j++) {
					answer[compo[vec[j-1]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[j-1]]]=1;
				}
				used1[i]=0;
			}
		}
		vector<bool> used2(m, 0);
		for (int i=0; i<m; i++) if (!used2[i] && !used1[i]) {
			vector<int> vec(1, i);
			for (int j=i; j<m; j++) {
				if (p[i][j]==2 && !used1[j]) vec.pb(j);
			}
			if (sz(vec)>1) {
				if (sz(vec)==2) return 0;
				for (auto &u: vec) used2[u]=1;
				for (int j=0; j<sz(vec); j++) {
					answer[compo[vec[(j+1)%sz(vec)]]][compo[vec[j]]]=answer[compo[vec[j]]][compo[vec[(j+1)%sz(vec)]]]=1;
				}
				used2[i]=0;
			}
		}
		vector<int> vec;
		for (int i=0; i<m; i++) {
			if (!used1[i] && !used2[i]) {
				vec.pb(i);
			}
		}
		if (sz(vec)<=1) continue;
		if (sz(vec)<=3) return 0;
		for (int i=0; i<sz(vec); i++) {
			answer[compo[vec[(i+1)%sz(vec)]]][compo[vec[i]]]=answer[compo[vec[i]]][compo[vec[(i+1)%sz(vec)]]]=1;
		}
		answer[compo[vec[0]]][compo[vec[sz(vec)-2]]]=answer[compo[vec[sz(vec)-2]]][compo[vec[0]]]=1;
	}
	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: 0 / 4