Submission #578058

#	Time	Username	Problem	Language	Result	Execution time	Memory
578058		1ne	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	416 ms	22396 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int>parent;
	vector<int>sz;
	vector<vector<int>>comp;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		comp.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
			comp[i].push_back(i);
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int a,int b){
		int u = findsets(a);
		int v = findsets(b);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		parent[v] = u;
		sz[u]+=sz[v];
		sz[v] = 0;
		while(!comp[v].empty()){
			comp[u].push_back(comp[v].back());
			comp[v].pop_back();
		}
		return true;
	}
};
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n,vector<int>(n,0));
	for (int i = 0;i<n;++i){
		for (int j = 0;j<n;++j){
			if (p[i][j] == 3)return 0;
		}
	}
	DSU st;
	st.build(n);
	for (int i = 0;i<n;++i){
		for (int j = i + 1;j<n;++j){
			int u = st.findsets(i);
			int v = st.findsets(j);
			if (p[i][j]==1 && st.unionset(i,j)){
				answer[u][v] = true;
				answer[v][u] = true;
			}
		}
	}
	vector<vector<bool>>pre(n,vector<bool>(n,false));
	vector<bool>wt(n,false);
	for (int i = 0;i<n;++i){
		for (int j = i + 1;j<n;++j){
			if (st.findsets(i) == st.findsets(j)){
				pre[i][j] = true;
				pre[j][i] = true;
				wt[i] = true;
				wt[j] = true;
			}
		}
	}
	for (int i = 0;i<n;++i){
		if (i == st.findsets(i))wt[i] = false;
	}
	vector<bool>visited(n,false);
	for (int i = 0;i<n;++i){
		if (i == st.findsets(i) && !visited[i]){
			vector<int>par(n,-1);
			function<void(int)> dfs = [&](int u){
				if (u == i && par[u]!=-1){
					int x = par[u];
					visited[u] = true;
					answer[u][x] = true;
					answer[x][u] = true;
					while(x != u){
						visited[x] = true;
						st.unionset(i,x);
						answer[x][par[x]] = true;
						answer[par[x]][x] = true;
						x = par[x];
					}
				}
				for (int j = 0;j<n;++j){
					if (j == u)continue;
					if (p[u][j]!=2)continue;
					if (wt[j])continue;
					if (j == par[u])continue;
					if (par[j]==-1){
						par[j] = u;
						dfs(j);
						par[j] =-1;
					}
				}
			};
			dfs(i);
		}
	}
	
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			for (int k = j + 1; k < n; k++){
				if (p[i][j] == 1 && p[j][k] == 1 && p[i][k] != 1) return 0;
			}
			if (p[i][j] == 0 && st.findsets(i) == st.findsets(j)) return 0;
		}
	}
	for (int i = 0;i < n;++i){
		for (int j = 0;j<n;++j){
			if (p[i][j] && st.findsets(i)!=st.findsets(j))return 0;
		}
	}
	build(answer);
	return 1;
}

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