Submission #697403

#	Time	Username	Problem	Language	Result	Execution time	Memory
697403		youngyojun	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	211 ms	28128 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef pair<int, int> pii;

int construct(vector<vector<int>> A) {
	int N = A.size();

	for(int i = N; i--;) for(int j = N; j--;)
		if(2 < A[i][j]) return 0;
	
	vector<int> B(N, -1);
	for(int i = 0; i < N; i++) if(B[i] < 0) {
		for(int j = i; j < N; j++) if(1 == A[i][j]) B[j] = i;
	}

	vector<vector<int>> Cy, Co;
	vector<bool> chk(N, false);

	for(int i = 0; i < N; i++) if(!chk[i]) {
		vector<int> V, U; V.eb(B[i]);
		for(int j = 0; j < N; j++) if(A[i][j]) {
			U.eb(j);
			if(1 == A[i][j]) {
				if(chk[j]) return 0;
				chk[j] = true;
			} else {
				if(chk[j]) return 0;
				chk[j] = true;
				V.eb(B[j]);
			}
		}
		sort(allv(V)); univ(V);
		if(2 == sz(V)) return 0;
		Cy.eb(V); Co.eb(U);
	}

	vector<vector<int>> D(N, vector<int>(N, 0));
	vector<pii> EV;

	for(int ci = 0, cn = sz(Cy); ci < cn; ci++) {
		auto &cycle = Cy[ci], &comp = Co[ci];

		for(int a : comp) for(int b : comp) D[a][b] = 2;
		for(int r : cycle) {
			vector<int> V;
			for(int v : comp) if(r == B[v]) V.eb(v);
			for(int v : V) EV.eb(r, v);
			for(int a : V) for(int b : V) D[a][b] = 1;
		}

		int L = sz(cycle);
		if(1 < L) {
			for(int i = 0, j = 1; i < L; i++, j++) {
				if(j == L) j = 0;
				EV.eb(cycle[i], cycle[j]);
			}
		}
	}

	for(int i = 0; i < N; i++) if(D[i] != A[i]) return 0;

	vector<vector<int>> ret(N, vector<int>(N, 0));
	for(auto [a, b] : EV) if(a != b) ret[a][b] = ret[b][a] = 1;

	build(ret);
	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