Submission #306213

#	Time	Username	Problem	Language	Result	Execution time	Memory
306213		sofapuden	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	259 ms	22360 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> ufa;

int uf(int ind){
	if(ufa[ind] == ind)return ind;
	return ufa[ind] = uf(ufa[ind]);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	ufa.resize(n);
	iota(ufa.begin(), ufa.end(), 0);
	vector<vector<int>> tog(n);
	vector<vector<int>> out(n, vector<int> (n,0));
	vector<vector<int>> tre(n);
	
	for(auto i : p)for(auto x : i)if(x==3)return 0;
	
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(p[i][j]){
				int a = uf(i);
				int b = uf(j);
				if(a == b)continue;
				ufa[uf(i)] = ufa[uf(j)];
			}
		}
	}
	for(int i = 0; i < n; ++i){
		tog[uf(i)].push_back(i);
	}
	iota(ufa.begin(), ufa.end(), 0);
	
	for(int i = 0; i < n; ++i){
		for(auto x : tog[i]){
			for(auto y : tog[i]){
				if(p[x][y] == 0)return 0;
				if(p[x][y] == 1){
					int a = uf(x);
					int b = uf(y);
					if(a == b)continue;
					ufa[uf(x)] = ufa[uf(y)];
				}
			}
		}
		vector<int> cy;
		for(auto x : tog[i]){
			tre[uf(x)].push_back(x);
			if(x == uf(x))cy.push_back(x);
		}
		if(cy.size() == 1)continue;
		if(cy.size() == 2)return 0;
		
		int cn = 1;
		for(int j = 0; j < (int)cy.size(); ++j){
			if(cn == (int)cy.size())cn = 0;
			out[cy[j]][cy[cn]] = out[cy[cn]][cy[j]] = 1;
			cn++;
		}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 1; j < (int)tre[i].size(); ++j){
			out[tre[i][0]][tre[i][j]] = out[tre[i][j]][tre[i][0]] = 1;
		}
	}
	build(out);	
	return 1;
}

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