Submission #431167

#	Time	Username	Problem	Language	Result	Execution time	Memory
431167		saleh	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	280 ms	22340 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 1000 + 23;

vector<int> v[MAXN], v2[MAXN];
set<int> r, r2;
int n, num1[MAXN], num2[MAXN];// par[MAXN],
bitset<MAXN> b2[MAXN];


int construct(vector<vector<int>> p) {
	n = p.size();
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0;
	for (int i = 0; i < n; i++) r.insert(i), v[i].push_back(i);
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 1) num1[i]++;
	for (int i = 0; i < n; i++) if (r.find(i) != r.end()) for (int j = i + 1; j < n; j++) if (r.find(j) != r.end()) if (p[i][j] == 1) {
		while (v[j].size()) {
//			par[v[j].back()] = i;
			v[i].push_back(v[j].back());
			v[j].pop_back();
		}
		r.erase(j);
	}
	vector<vector<int>> ans;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for (auto i : r) r2.insert(i), v2[i].push_back(i);
	for (auto i : r) {
		for (auto j : v[i]) for (auto k : v[i]) if (p[k][j] != 1) return 0;
		for (auto j : v[i]) if (num1[j] != (int)v[i].size()) return 0;
		for (int j = 1; j < (int)v[i].size(); j++) ans[v[i][j - 1]][v[i][j]] = ans[v[i][j]][v[i][j - 1]] = 1;
	}
	for (auto i : r) for (auto j : r) if (i < j) {
		int tmp = 0;
		for (auto a : v[i]) for (auto b : v[j]) tmp |= (1 << p[a][b]);
		if (tmp == 5) return 0;
		if (tmp == 4) b2[i][j] = b2[j][i] = true;
		num2[i]++;
		num2[j]++;
	}
	for (auto i : r) if (r2.find(i) != r2.end()) for (auto j : r) if (i < j && r2.find(j) != r2.end()) if (b2[i][j]) {
		while (v2[j].size()) {
			v2[i].push_back(v2[j].back());
			v2[j].pop_back();
		}
		r2.erase(j);	
	}
	for (auto i : r2) {
		if (v2[i].size() < 2) continue;
		for (auto j : v2[i]) for (auto k : v2[i]) if (j != k && !b2[k][j]) return 0;
		for (auto j : v2[i]) if (num2[j] != (int)v2[i].size() - 1) return 0;
		if (v2[i].size() == 2) return 0;
		for (int j = 1; j < (int)v2[i].size(); j++) ans[v2[i][j - 1]][v2[i][j]] = ans[v2[i][j]][v2[i][j - 1]] = 1;
		ans[v2[i][v2[i].size() - 1]][v2[i][0]] = ans[v2[i][0]][v2[i][v2[i].size() - 1]] = 1;
	}
//	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (ans[i][j] == true) cout << i << ' ' << j << endl;
	build(ans);
	return 1;
}
//int main() {cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});}

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