Submission #304544

#	Time	Username	Problem	Language	Result	Execution time	Memory
304544		SorahISA	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	265 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
 
struct DSU {
	vector<int> s, p;
	DSU(int sz) : s(sz + 1, 1), p(sz + 1, -1) {}
	int find(int x) {
		return (p[x] == -1) ? x : (p[x] = find(p[x]));
	}
	bool join(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(s[x] < s[y]) swap(x, y);
		s[x] += s[y]; p[y] = x;
		return true;
	}
};
 
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	DSU loli(n);
	auto add = [&](int x, int y) {
		x = loli.find(x);
		y = loli.find(y);
		if(x == y) return;
		answer[x][y] = 1;
		answer[y][x] = 1;
		loli.join(x, y);
	};
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 1) {
				add(i, j);
			}
          if (p[i][j] == 3) return 0;
		}
	}
	vector<int> keep;
	vector<bool> vis(n);
	function<void(int)> dfs = [&](int x) {
		vis[x] = true;
		keep.push_back(x);
		for(int i = 0; i < n; i++) {
			int y = loli.find(i);
			if(p[x][y] && !vis[y]) dfs(y);
		}
	};
	for(int i = 0; i < n; i++) {
		int x = loli.find(i);
		if(!vis[x]) {
			keep.clear(); dfs(x);
			if(keep.size() == 1) continue;
          	if(keep.size() == 2) return 0;
			for(int j = 1; j < (int)keep.size(); j++) {
				answer[keep[j]][keep[j - 1]] = 1;
				answer[keep[j - 1]][keep[j]] = 1;
			}
			answer[keep[0]][keep.back()] = 1;
			answer[keep.back()][keep[0]] = 1;
			for(int x : keep) {
				for(int y : keep) {
					if(x == y) continue;
					if(p[x][y] != 2) return 0;
				}
			}
		}			
	}
	vector<vector<int>> T(n); 
	for(int i = 0; i < n; i++) {
		T[loli.find(i)].push_back(i);
	}
	for(int i = 0; i < n; i++) {
		for(int x : T[i]) {
			for(int y : T[i]) {
				if(p[x][y] != 1) return 0;
			}
		}
	}
	/*for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cout << answer[i][j] << " \n"[j == n - 1];
		}
	}*/
	build(answer);
	return 1;
}

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