Submission #1050269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050269		MercubytheFirst	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	107 ms	24188 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;


struct DSU
{
	int n = -37;
	vector<int> par;
	DSU(int sz) : n(sz) {
		par.assign(n, -1);
	}

	int get(int x) {
		return (par[x] < 0 ? x : par[x] = get(par[x]));
	}

	bool merge(int x, int y) {
		x = get(x);
		y = get(y);
		if(x == y) {
			return false;
		}
		assert(par[x] < 0 and par[y] < 0);
		if(par[x] > par[y]) {
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	DSU single(n);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < i; ++j) {
			if(p[i][j] == 1) {
				single.merge(i, j);
			}
		}
	}
	// cout << "Single\n---------\n";
	// for(int i = 0; i < n; ++i) {
	// 	cout << i << " : " << single.get(i) << endl;
	// }
	DSU cycles = single;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < i; ++j) {
			if(p[i][j] == 2) {
				if(single.get(i) == single.get(j)) {
					return 0;
				}
				cycles.merge(i, j);
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < i; ++j) {
			if(p[i][j] == 0) {
				if(single.get(i) == single.get(j) or cycles.get(i) == cycles.get(j)) {
					return 0;
				}
			}
		}
	}
	vector<vector<int> > lines(n), answer(n, vector<int>(n)), circles(n);
	for(int i = 0; i < n; ++i) {
		lines[single.get(i)].push_back(i);
	}
	for(int i = 0; i < n; ++i) {
		const int sz = lines[i].size();
		// cout << "Line : ";
		// for(int x : lines[i]) {
		// 	cout << x << ' ';
		// }cout << endl;
		for(int j = 1; j < sz; ++j) {
			int prev = lines[i][j - 1], cur = lines[i][j];
			answer[prev][cur] = answer[cur][prev] = 1;
		}
	}
	for(int i = 0; i < n; ++i) {
		if(single.get(i) != i) {
			continue;
		}
		circles[cycles.get(i)].push_back(i);
	}
	// cout << "Cycle\n------------\n";
	// for(int i = 0; i < n; ++i) {
	// 	cout << i << " : " << cycles.get(i) << endl;
	// }
	for(int i = 0; i < n; ++i) {
		if(circles[i].size() < 2u) {
			continue;
		}
		if(circles[i].size() == 2u) {
			return 0;
		}
		const int sz = circles[i].size();
		for(int j = 0; j < sz; ++j) {
			int cur = circles[i][j], to = circles[i][(j + 1) % sz];
			assert(answer[cur][to] == answer[to][cur] and answer[cur][to] == 0);
			answer[cur][to] = answer[to][cur] = 1;
		}
	}
	build(answer);
	return 1;
}


/*
4
1 1 2 2 
1 1 2 2
2 2 1 2
2 2 2 1

2
1 0
0 1

2
1 2
2 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