Submission #304538

#	Time	Username	Problem	Language	Result	Execution time	Memory
304538		SorahISA	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	268 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) {}
  	void init() {
      	iota(p.begin(), p.end(), 0);
    }
	int find(int x) {
		return (p[x] == x) ? 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);
  	loli.init();
	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);
			}
		}
	}
	vector<int> keep;
	vector<bool> vis(n);
	vector<vector<int>> T(n);
	for(int i = 0; i < n; i++) {
		T[loli.find(i)].push_back(i);
	}
	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) {
				int a = keep[0];
				int b = keep[1];
				if(T[a].size() == 1 && T[b].size() == 1) return 0;
				if(T[a].size() > T[b].size()) swap(a, b); 
				answer[T[a][0]][T[b][0]] = 1;
				answer[T[b][0]][T[a][0]] = 1;
				answer[T[a][0]][T[b][1]] = 1;
				answer[T[b][1]][T[a][0]] = 1;
			}
			else {
				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 i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] == 0) continue;
			if(loli.find(i) == loli.find(j)) {
				if(p[i][j] != 1) return 0;
			} else {
				if(p[i][j] != 2) 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: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4