Submission #386819

#	Time	Username	Problem	Language	Result	Execution time	Memory
386819		ZikXewen	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	276 ms	24188 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int X = 1005;
int p[X], ls[X];
int fd(int u){return p[u] = ((p[u] == u)? u : fd(p[u]));}
vector<vector<int>> an;
void un(int u, int v){
	u = fd(u), v = fd(v);
	if(u == v) return;
	an[u][ls[v]] = an[ls[v]][u] = 1; p[u] = v; ls[v] = ls[u];
}
int construct(vector<vector<int>> ar) {
	int N = ar.size();
	an.assign(N, vector<int>(N, 0));
	iota(p, p + N, 0), iota(ls, ls + N, 0);
	for(int i = 0; i < N; ++i) for(int j = i + 1; j < N; ++j){
		if(ar[i][j] == 3 or ar[i][j] != ar[j][i]) return 0;
		if(ar[i][j] == 1) un(i, j);
	}
	for(int i = 0; i < N; ++i) for(int j = i + 1; j < N; ++j){
		int pi = fd(i), pj = fd(j);
		if(ar[i][j] != 1 and pi == pj) return 0;
	}
	for(int i = 0; i < N; ++i) if(fd(i) == i) ls[i] = i;
	for(int i = 0; i < N; ++i) for(int j = i + 1; j < N; ++j) if(ar[i][j] == 2) un(i, j);
	for(int i = 0; i < N; ++i) if(fd(i) == i and ls[i] != i) an[ls[i]][i] = an[i][ls[i]] = 1;
	build(an);
	return 1;
}

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