Submission #400808

#	Time	Username	Problem	Language	Result	Execution time	Memory
400808		shivensinha4	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	283 ms	30328 KiB

supertrees

#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'

bool valid = true;
vi singleComp;
vector<vi> answer, paths, doubleAdj, compEl; // da: -1: dunno, 0: nope, 1: yep
int n;

void dfs(int p, vi &comp, vector<vi> &adj) {
	compEl[comp[p]].push_back(p);
	for_(i, 0, n) if (p != i and adj[p][i] == 1) {
		if (comp[i] == -1) {
			comp[i] = comp[p];
			dfs(i, comp, adj);
		}
		
		if (comp[i] != comp[p]) valid = false;
	}
}

bool checkDouble(int a, int b) {
	for (auto x: compEl[a]) for (auto y: compEl[b]) if (paths[x][y] != 2) return false;
	
	return true;
}

int construct(vector<vi> p) {
	paths = p;
	n = paths.size();
	answer.resize(n, vi(n)); singleComp.resize(n, -1); doubleAdj.resize(n, vi(n, -1)); compEl.resize(n);
	
	for_(i, 0, n) if (singleComp[i] == -1) {
		singleComp[i] = i;
		dfs(i, singleComp, paths);
	}
	
	for_(i, 0, n) for_(j, i+1, n) if (paths[i][j] == 2) {
		if (singleComp[i] == singleComp[j]) {
			valid = false;
			continue;
		}
		
		int a = singleComp[i], b = singleComp[j];
		if (doubleAdj[a][b] == -1) {
			doubleAdj[a][b] = doubleAdj[b][a] = checkDouble(a, b);
			if (!doubleAdj[a][b]) valid = false;
		}
	}
		
	compEl.assign(n, {});
	vi doubleComp(n, -1);
	for_(i, 0, n) if (singleComp[i] == i and doubleComp[i] == -1) {
		doubleComp[i] = i;;
		dfs(i, doubleComp, doubleAdj);
	}
	
	for_(i, 0, n) for_(j, i+1, n) {
		if (singleComp[i] != singleComp[j] and (paths[i][j] == 2 or doubleComp[singleComp[i]] == doubleComp[singleComp[j]])) {
			valid = valid and paths[i][j] == 2 and doubleComp[singleComp[i]] == doubleComp[singleComp[j]];
		}
		
		if (paths[i][j] == 0) valid = valid and singleComp[i] != singleComp[j] and doubleComp[singleComp[i]] != doubleComp[singleComp[j]];
		else if (paths[i][j] == 1) valid = valid and singleComp[i] == singleComp[j];
		else if (paths[i][j] == 2) valid = valid and singleComp[i] != singleComp[j] and doubleComp[singleComp[i]] == doubleComp[singleComp[j]];
		else valid = false;
	}
	
	for_(i, 0, n) for_(j, i+1, n) if (singleComp[i] == i and singleComp[j] == j and doubleComp[i] == doubleComp[j]) valid = valid and checkDouble(i, j);
	
	
	if (!valid) return 0;
	
	for_(i, 0, n) if (singleComp[i] != i) answer[i][singleComp[i]] = answer[singleComp[i]][i] = 1;
	
	for_(i, 0, n) if (compEl[i].size() > 1) {
		int s = compEl[i].size();
		for_(j, 0, s) {
			int nxt = j == s-1 ? 0 : j+1;
			answer[compEl[i][j]][compEl[i][nxt]] = answer[compEl[i][nxt]][compEl[i][j]] = 1;
		}
	}
	
	build(answer);
	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