Submission #1205763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205763		ansori	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	119 ms	22304 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 5;
void build(std::vector<std::vector<int>> _b) ;
vector<int> sn0[N] , sn1[N];
int fa0[N] , fa1[N];
vector<int> f;
void unit0(int v , int u){
	v = fa0[v] , u = fa0[u];
	if(v == u) return ;
	if(sn0[v].size() < sn0[u].size()) swap(u , v);
	sn1[u].clear();
	while(sn0[u].size()){
		sn0[v].push_back(sn0[u].back());
		fa0[sn0[u].back()] = v;
		sn0[u].pop_back();
	}
}
void unit1(int v , int u){
	v = fa1[v] , u = fa1[u];
	if(v == u) return ;
	if(sn1[v].size() < sn1[u].size()) swap(u , v);
	while(sn1[u].size()){
		sn1[v].push_back(sn1[u].back());
		fa1[sn0[u].back()] = v;
		sn1[u].pop_back();
	}
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n , vector<int> (n , 0));
	f = vector<int> (n , 1);
	for(int i = 0;i < n; ++ i){
		fa0[i] = fa1[i] = i;
		sn0[i] = sn1[i] = {i};
	}
	for(int i = 0;i < n; ++ i){
		for(int j = 0;j < n; ++ j){
			if(p[i][j] == 1){
				unit0(i , j);
			}	
		}
	}
	for(int i = 0;i < n; ++ i){
		for(auto to : sn0[i]){
			if(to == i) continue ;
			answer[to][i] = 1;
			answer[i][to] = 1;
		}		
	}
	for(int i = 0;i < n; ++ i){
		for(int j = 0;j < n; ++ j){
			if(p[i][j] > 1){
				unit1(fa0[i] , fa0[j]);
			}
		}
	}
	for(int i = 0;i < n; ++ i){
		if(sn1[i].size() == 0) continue ;
		int sz = sn1[i].size() , k = 1;
		if(sz > 1){
			k = p[sn1[i][0]][sn1[i][1]];
		}
		for(int j = 0;j < sz - 1; ++ j){
			answer[sn1[i][j]][sn1[i][j + 1]] = 1;
			answer[sn1[i][j + 1]][sn1[i][j]] = 1;
		}
		f[i] = k;
		if(k > 1){
			k --;
			if(sz > 2){
				answer[sn1[i][0]][sn1[i][2]] = 1;
				answer[sn1[i][2]][sn1[i][0]] = 1;
			}
			else return 0;
		}
		if(k > 1){
			k --;
			if(sz > 3){
				answer[sn1[i][0]][sn1[i][3]] = 1;
				answer[sn1[i][3]][sn1[i][0]] = 1;
			}
			else return 0;
		}
	}
	bool ok = true;
	for(int i = 0;i < n;++ i){
		for(int j = 0;j < n; ++ j){
			int cnt = 0;
			if(fa0[i] == fa0[j]) cnt = 1;
			else if(fa1[fa0[i]] == fa1[fa0[j]]){
				cnt = f[fa1[fa0[i]]];
			}
			ok &= (p[i][j] == cnt);
		}
	}
	if(ok) build(answer);
	return ok;
}

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