Submission #832999

#	Time	Username	Problem	Language	Result	Execution time	Memory
832999		Halym2007	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	189 ms	26016 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define pb push_back
#define sz size()
const int N = 1005;
int a[N][N], a1, par[N], par1[N];
vector <int> q;
vector<vector<int>> answer;


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

void uni (int x, int y) {
	x = get (x);
	y = get (y);
	par[max (x, y)] = min(x, y);
}



int get1 (int x) {
	if (x == par1[x]) return x;
	return par1[x] = get1 (par1[x]);
}

void uni1 (int x, int y) {
	x = get1 (x);
	y = get1 (y);
	par1[max (x, y)] = min (x, y);
}


int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; ++i) {
		par[i] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			assert (p[i][j] == p[j][i]);
			if (i == j) continue;
			if (p[i][j] == 3) return 0;
			if (p[i][j]) {
				uni (i, j);
			}
			a1 = max (a1, p[i][j]);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			if (!p[i][j] and get(i) == get(j)) return 0;
		}
	}
	
	for (int i = 0; i < n; ++i) {
		q.clear();
		for (int j = 0; j < n; ++j) {
			if (get(j) == i) q.pb (j);
		}
		if ((int)q.sz == 0) continue;
		for (int i = 0; i < n; ++i) par1[i] = i;
		for (int ii = 0; ii < (int)q.sz; ++ii) {
			for (int jj = 0; jj < (int)q.sz; ++jj) {
				if (ii == jj) continue;
				if (p[q[ii]][q[jj]] == 1) {
					uni1(ii, jj);
				}
			}
		}
		vector <vector <int>> g((int)q.sz);
		for (int j = 0; j < (int)q.sz; ++j) {
			g[get1(j)].pb (q[j]);
		}
		vector <int> h;
		for (int j = 0; j < (int)g.sz; ++j) {
			if ((int)g[j].sz) {
				h.pb (g[j][0]);
			}
			for (int k = 0; k + 1< (int)g[j].sz; ++k) {
				a[g[j][k]][g[j][k + 1]] = 1;
				a[g[j][k + 1]][g[j][k]] = 1;
			}
		}
		if ((int)h.sz == 2 and a1 == 2) return 0;
		if ((int)h.sz > 2 and a1 == 2) {
		  if (!h.empty()) h.pb (h[0]);
			for (int j = 0; j < (int)h.sz - 1; ++j) {
				a[h[j]][h[j + 1]] = 1;
				a[h[j + 1]][h[j]] = 1;
			}
		}
	
	}
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		for (int j = 0; j < n; ++j) {
			if (a[i][j]) row[j] = 1;
		}
		answer.push_back(row);
	}
	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: 4 / 4