Submission #342325

#	Time	Username	Problem	Language	Result	Execution time	Memory
342325		DrearyJoke	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	284 ms	24428 KiB

supertrees

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "supertrees.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}

#define deb(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define END '\n'
#define inf 9e18
#define ff first
#define ss second
#define pb push_back

const int maxN = 1000;

int parent[maxN][4], sz[maxN][4];

int find_parent(int a, int con) {
	if (parent[a][con] == a) return a;
	else return parent[a][con] = find_parent(parent[a][con], con);
}

void merge(int a, int b, int con) {
	a = find_parent(a, con);
	b = find_parent(b, con);
	if (a == b) return;
	if (sz[a][con] < sz[b][con]) swap(a, b);
	parent[b][con] = a;
	sz[a][con] += sz[b][con];
}

bool same_set(int a, int b, int con) {
	a = find_parent(a, con);
	b = find_parent(b, con);
	return a == b;
}

void make_set(int n) {
	for (int i = 0; i < n; ++i) {
		for (int j = 1; j <= 3; ++j) {
			parent[i][j] = i;
			sz[i][j] = 1;
		}
	}
}

int construct(vvi p) {
	int n = p.size();
	vvi A(n, vi(n, 0));
	make_set(n);
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (p[i][j] == 1) merge(i, j, p[i][j]);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (!p[i][j] && same_set(i, j, 1)) return 0;
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			int a = find_parent(i, 1), b = find_parent(j, 1);
			if (p[i][j] > 1) {
				if (a == b) return 0;
				merge(a, b, p[i][j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			int a = find_parent(i, 1), b = find_parent(j, 1);
			if (!p[i][j] && (same_set(i, j, 2) || same_set(a, b, 2) || same_set(i, j, 3) || same_set(a, b, 3))) return 0;
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	for (int j = i + 1; j < n; ++j) {
	// 		int cnt = 0;
	// 		int a = find_parent(i, 1), b = find_parent(j, 1);
	// 		for (int k = 1; k <= 3; ++k) {
	// 			cnt += same_set(a, b, k);
	// 		}
	// 		if (cnt > 1) {
	// 			cout << "LOL: " << i << " " << j << " " << cnt << END;
	// 			return 0;
	// 		}
	// 	}
	// }
	vector<vvi> comps(4, vvi(n));
	for (int i = 0; i < n; ++i) {
		int c = find_parent(i, 1);
		int a = find_parent(c, 2), b = find_parent(c, 3);
		if (sz[a][2] > 1 && sz[b][3] > 1) return 0;
		if (sz[a][2] == 2) return 0;
		if (sz[b][3] > 1 && sz[b][3] < 4) return 0;
		comps[1][c].pb(i);
		if (c == i)
		comps[2][a].pb(i);
		if (c == i)
		comps[3][b].pb(i);
	}
	for (int i = 0; i < n; ++i) {
		if ((int)comps[1][i].size() <= 1) continue;
		for (int j = 1; j < (int)comps[1][i].size(); ++j) {
			int a = comps[1][i][j], b = comps[1][i][j - 1];
			if (a == b) {
				cout << "FUCK";
			}
			A[a][b] = A[b][a] = 1;
		}
	}
	for (int i = 0; i < n; ++i) {
		if ((int)comps[2][i].size() <= 1) continue;
		for (int j = 1; j < (int)comps[2][i].size(); ++j) {
			int a = comps[2][i][j], b = comps[2][i][j - 1];
			if (a == b) {
				cout << "DAMN";
			}
			A[a][b] = A[b][a] = 1;
		}
		int a = comps[2][i][0], b = comps[2][i].back();
		A[a][b] = A[b][a] = 1;
		if (a == b) {
			cout << "DAMN_ME";
		}
	}
	for (int i = 0; i < n; ++i) {
		if ((int)comps[3][i].size() <= 1) continue;
		for (int j = 1; j < (int)comps[3][i].size(); ++j) {
			int a = comps[3][i][j], b = comps[3][i][j - 1];
			if (a == b) {
				cout << "WOW";
			}
			A[a][b] = A[b][a] = 1;
		}
		int a = comps[3][i][0], b = comps[3][i].back(), c = comps[3][i][1];
		if (b == c) {
			cout << "WOW_ME";
		}
		A[a][b] = A[b][a] = 1;
		A[b][c] = A[c][b] = 1;
	}
	build(A);
	return 1;
}

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