Submission #360217

#	Time	Username	Problem	Language	Result	Execution time	Memory
360217		NachoLibre	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	269 ms	28268 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "supertrees.h"
#else
void build(vector<vector<int>> b) {
	int n = b.size();
	cout << "________" << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cout << b[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for(int i = 0; i < n; ++i) {
		for(int j = i; j < n; ++j) {
			if(b[i][j]) {
				cout << i << " - " << j << endl;
			}
		}
	}
}
#endif

const int N = 1003;
int dop[N];
int P(int x) {
	return (dop[x] ^ -1 ? dop[x] = P(dop[x]) : x);
}
void U(int x, int y) {
	dop[P(x)] = (P(x) ^ P(y) ? P(y) : -1);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> b(n);
	for(int i = 0; i < n; ++i) {
		dop[i] = -1;
		b[i].resize(n);
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(p[i][j] == 3) return 0;
			if(p[i][j] == 1) U(i, j);
		}
	}
	vector<int> dopn(n, -1), ep(n);
	vector<vector<int>> v;
	for(int i = 0; i < n; ++i) {
		ep[i] = P(i);
		if(dopn[P(i)] == -1) {
			dopn[P(i)] = v.size();
			v.push_back({});
		}
		v[dopn[P(i)]].push_back(i);
		if(p[v[dopn[P(i)]][0]] != p[i]) return 0;
	}
	int m = v.size();
	for(int i = 0; i < m; ++i) {
		for(int j = 1; j < (int)v[i].size(); ++j) {
			b[v[i][j - 1]][v[i][j]] = 1;
			b[v[i][j]][v[i][j - 1]] = 1;
		}
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < m; ++i) {
		dop[i] = -1;
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(p[i][j] == 2) U(dopn[ep[i]], dopn[ep[j]]);
		}
	}
	vector<vector<int>> q = p;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(q[i][j] == 1) q[i][j] = 2;
		}
	}
	vector<int> dopm(n, -1);
	vector<vector<int>> u;
	for(int i = 0; i < m; ++i) {
		if(dopm[P(i)] == -1) {
			dopm[P(i)] = u.size();
			u.push_back({});
		}
		u[dopm[P(i)]].push_back(i);
		if(q[v[u[dopm[P(i)]][0]][0]] != q[v[i][0]]) return 0;
	}
	int k = u.size();
	for(int i = 0; i < k; ++i) {
		if(u[i].size() == 1) continue;
		if(u[i].size() == 2) return 0;
		for(int j = 1; j < (int)u[i].size(); ++j) {
			int x = u[i][j], y = u[i][j - 1];
			b[v[x][0]][v[y][0]] = 1;
			b[v[y][0]][v[x][0]] = 1;
		}
		int x = u[i][0], y = u[i][(int)u[i].size() - 1];
		b[v[x][0]][v[y][0]] = 1;
		b[v[y][0]][v[x][0]] = 1;
	}
	build(b);
	return 1;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}}) << endl << "________" << endl;
	cout << construct({{1, 0}, {0, 1}}) << endl << "________" << endl;
	cout << construct({{1, 3}, {3, 1}}) << endl << "________" << endl;
	return 0;
}
#endif

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