Submission #794292

#	Time	Username	Problem	Language	Result	Execution time	Memory
794292		MODDI	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	183 ms	22164 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
struct DSU{
	vi parent, size;
	vector<bool> kec, dvojka;
	void init(int n){
		kec.resize(n, false);
		dvojka.resize(n, false);
		for(int i = 0; i < n; i++){
			parent.pb(i);
			size.pb(1);
		}
	}
	bool is_dva(int v){
		return dvojka[v];
	}
	int get_size(int v){
		return size[v];
	}
	int find_parent(int v){
		if(parent[v] == v)	return v;
		return parent[v] = find_parent(parent[v]);
	}
	void merge(int a, int b, int tip){
		a = find_parent(a);
		b = find_parent(b);
		bool done = false;
		if(a != b){
			if(size[b] > size[a])
				swap(a, b);
			
			done = true;
			if(tip == 1)	kec[a] = true;
			if(tip == 2)	dvojka[a] = true;	
			parent[b] = a;
			size[a] += size[b];
		}
		if(!done){
			if(tip == 1)	kec[a] = true;
			if(tip == 2) 	dvojka[a] = true;
		}
	}
};
int construct(vector<vi> p) {
	int n = p.size();
	vector<vi> answer;
	bool possible = true;
	for(int i = 0; i < n; i++){
		for(auto t : p[i]){
			if(t == 3)	possible = false;
		}
	}
	for(int i = 0; i < n; i++){
		vi pom(n,0);
		answer.pb(pom);
	}
	DSU dsu1, dsu2;
	dsu1.init(n);
	dsu2.init(n);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(p[i][j] ==  1)
				dsu1.merge(i, j, 1);
			else if(p[i][j] == 2)
				dsu2.merge(i, j, 2);
		}
	}
	//assert(false);
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(dsu1.find_parent(i) == dsu1.find_parent(j) && p[i][j] == 0)
				possible = false;
			if(dsu2.find_parent(i) == dsu2.find_parent(j) && p[i][j] == 0)
				possible = false;
			if(p[i][j] == 2 && dsu1.find_parent(i) == dsu1.find_parent(j))
				possible = false;
		}
	}
	//assert(false);
	int first[n], last[n];
	memset(first, -1, sizeof first);
	memset(last, -1, sizeof last);
	for(int i = 0; i < n; i++){
		int a = dsu2.find_parent(i);
		//cout<<i<<" "<<a<<endl;
		if(last[a] == -1){
			last[a] = i;
			first[a] = i;
		}
		else{
			//cout<<"HERE"<<endl;
			answer[i][last[a]] = 1;
			answer[last[a]][i] = 1;
			last[a] = i;
		}
	}
	//assert(false);
	for(int i = 0; i < n; i++){
		int a = dsu2.find_parent(i);
		if(dsu2.get_size(a) < 3 && dsu2.get_size(a) > 1)	possible = false;
		else if(dsu2.get_size(a) >= 3){
			answer[last[a]][first[a]] = 1;
			answer[first[a]][last[a]] = 1;
		}
	}
	memset(last, -1, sizeof last);
	for(int i = 0; i < n; i++){
		int a = dsu1.find_parent(i);
		if(last[a] == -1)	last[a] = i;
		else{
			//cout<<i<<" "<<last[a]<<" "<<endl;
			answer[i][last[a]] = 1;
			answer[last[a]][i] = 1;
		}
	}
	if(!possible)	return 0;
	build(answer);
	return 1;
}

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