Submission #794218

#	Time	Username	Problem	Language	Result	Execution time	Memory
794218		MODDI	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	193 ms	24012 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 ok(int v){
		if(dvojka[v] && kec[v])	return false;
		return true;
	}
	bool is_dva(int v){
		return dvojka[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 dsu;
	dsu.init(n);
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(p[i][j]>=1 && p[i][j]<=2){
				dsu.merge(i, j, p[i][j]);
				dsu.merge(j, i, p[i][j]);
			}
			else
				continue;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(p[i][j] == 0 && dsu.find_parent(i) == dsu.find_parent(j)){
				possible = false;
			}
		}
	}
	for(int i = 0; i < n; i++){
		int a = dsu.find_parent(i);
		if(!dsu.ok(a))
			possible = false;
	}
	int last[n], first[n];
	memset(first, -1, sizeof first);
	memset(last, -1, sizeof last);
	for(int i = 0; i < n; i++){
		int a = dsu.find_parent(i);
		if(last[a] == -1){	
			last[a] = i;
			first[a] = i;
		}
		else{
			answer[i][last[a]] = 1;
			answer[last[a]][i] = 1;
			last[a] = i;
		}
	}
	for(int i = 0; i < n; i++){
		int a = dsu.find_parent(i);
		if(dsu.is_dva(a)){
			answer[first[a]][last[a]] = 1;
			answer[last[a]][first[a]] = 1;
 		}
	}
	if(!possible)	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