Submission #302744

#	Time	Username	Problem	Language	Result	Execution time	Memory
302744		cgiosy	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	265 ms	22292 KiB

supertrees

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

#define R(i,n,...) for(int i=__VA_ARGS__+0; i<(n); ++i)
int construct(vector<vector<int>> A) {
	const int N=A.size();
	R(i, N) R(j, N) if(A[i][j]==3 || A[i][j]!=A[j][i]) return 0;

	int M=0, K=0;
	vector<int> X(N, -1), Y(N, -1);
	vector<vector<int>> G(N), H(N), E(N, vector<int>(N));
	function<void(int)> f1=[&](int i) {
		G[X[i]=M].push_back(i);
		R(j, N) if(A[i][j]==1 && !~X[j]) f1(j);
	};
	function<void(int)> f2=[&](int i) {
		H[Y[i]=K].push_back(i);
		R(j, N) if(A[i][j]==2 && !~Y[X[j]]) f2(X[j]);
	};
	auto con=[&](int i, int j) {
		E[i][j]=E[j][i]=1;
	};
	R(i, N) if(!~X[i]) f1(i), M++;
	R(i, M) if(!~Y[i]) f2(i), K++;
	for(auto&v:G) {
		const int L=v.size();
		if(!L) continue;
		for(int i:v) for(int j:v) if(A[i][j]!=1) return 0;
		R(i, L, 1) con(v[i], v[i-1]);
	}
	for(auto&v:H) {
		const int L=v.size();
		if(L<=1) continue;
		if(L==2) return 0;
		for(int i:v) for(int j:v) if(i!=j) for(int k:G[i]) for(int l:G[j]) if(A[k][l]!=2) return 0;
		R(i, L, 1) con(G[v[i]][0], G[v[i-1]][0]);
		con(G[v[0]][0], G[v[L-1]][0]);
	}
	build(E);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4