Submission #1239531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239531		AMnu	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	119 ms	22228 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3+5;

int N, P[2][MAXN];
vector<int> C[MAXN];
vector<vector<int>> ans;

int find(int t,int x) {
	if (P[t][x] == x) {
		return x;
	}
	return P[t][x] = find(t,P[t][x]);
}

void join(int t,int x,int y) {
	x = find(t,x);
	y = find(t,y);
	P[t][x] = y;
}

int construct(vector<vector<int>> D) {
	N = D.size();
	vector<int>row(N);
	for (int i=0;i<N;i++) {
		ans.push_back(row);
		P[0][i] = P[1][i] = i;
	}
	for (int i=0;i<N;i++) {
		for (int j=0;j<i;j++) {
			if (D[i][j] == 3) {
				return 0;
			}
			if (D[i][j]) {
				join(D[i][j]-1,i,j);
			}
		}
	}
	for (int i=0;i<N;i++) {
		for (int j=0;j<i;j++) {
			if (find(0,i) == find(0,j)) {
				if (D[i][j] != 1) {
					return 0;
				}
			}
			else if (find(1,i) == find(1,j)) {
				if (D[i][j] != 2) {
					return 0;
				}
			}
		}
	}
	for (int i=0;i<N;i++) {
		if (find(0,i) == i) {
			C[find(1,i)].push_back(i);
		}
		else {
			ans[i][find(0,i)] = ans[find(0,i)][i] = 1;
		}
	}
	for (int i=0;i<N;i++) {
		if (C[i].size() < 2) {
			continue;
		}
		if (C[i].size() == 2) {
			return 0;
		}
		for (int j=1;j<(int)C[i].size();j++) {
			ans[C[i][j]][C[i][j-1]] = ans[C[i][j-1]][C[i][j]] = 1;
		}
		ans[C[i].back()][C[i][0]] = ans[C[i][0]][C[i].back()] = 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