Submission #302957

#	Time	Username	Problem	Language	Result	Execution time	Memory
302957		rqi	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	267 ms	22300 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

#define sz(x) (int)(x).size()
#define pb push_back

struct DSU{
	vi e;
	void init(int n){
		e = vi(n, -1);
	}

	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}

	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};

const int mx = 1005;

int n;
vector<vi> p;
vector<vi> ans;
vi comps[mx];

vi lins[mx];

bool solve(vi comp){ //solve in sz(comp)*n time
	assert(sz(comp) > 0);



	vi incomp(n, 0);
	for(auto u: comp){
		incomp[u] = 1;
	}

	for(auto u: comp){
		for(int i = 0; i < n; i++){
			if(incomp[i] == 1){
				if(p[u][i] == 0) return 0; //component is not connected to anything
			}
			else{
				assert(p[u][i] == 0);
			}
		}
	}

	DSU dsu2;
	dsu2.init(sz(comp));

	vector<vi> subcomps(sz(comp), vi{});

	for(int i = 0; i < sz(comp); i++){
		for(int j = i+1; j < sz(comp); j++){
			if(p[comp[i]][comp[j]] == 1){
				dsu2.unite(i, j);
			}
		}
	}

	for(int i = 0; i < sz(comp); i++){
		subcomps[dsu2.get(i)].pb(i);
	}

	vi cyc;

	for(int i = 0; i < sz(comp); i++){
		if(sz(subcomps[i]) == 0) continue;
		vi insub(sz(comp), 0);
		for(auto u: subcomps[i]){
			insub[u] = 1;
		}
		for(auto u: subcomps[i]){
			for(int j = 0; j < sz(comp); j++){
				if(insub[j] == 1){
					if(p[comp[u]][comp[j]] != 1) return 0;
				}
				else{
					if(p[comp[u]][comp[j]] != 2) return 0;
				}
			}
		}

		for(int j = 0; j+1 < sz(subcomps[i]); j++){
			int a = comp[subcomps[i][j]];
			int b = comp[subcomps[i][j+1]];
			ans[a][b] = 1;
			ans[b][a] = 1;
		}

		cyc.pb(comp[subcomps[i][0]]);
	}

	if(sz(cyc) == 2) return 0;

	if(sz(cyc) >= 3){
		for(int i = 0; i < sz(cyc); i++){
			int a = cyc[i];
			int b = cyc[(i+1) % sz(cyc)];
			assert(a != b);
			ans[a][b] = 1;
			ans[b][a] = 1;
		}
	}

	// if(sz(cyc))

	// bool SUB3 = 1;
	// for(auto u1: comp){
	// 	for(auto u2: comp){
	// 		assert(p[u1][u2] != 0);
	// 		if(p[u1][u2] != 2) SUB3 = 0;
	// 	}
	// }

	// if(SUB3){
	// 	vi incomp(n, 0);
	// 	for(auto u: comp) incomp[u] = 1;
	// 	for(auto u: comp){
	// 		for(int i = 0; i < n; i++){
	// 			if(incomp[i] == 0){
	// 				assert(p[u][i] == 0);
	// 			}
	// 			else{
	// 				assert(p[u][i] == 2);
	// 			}
	// 		}
	// 	}
	// }

	return 1;
}

int construct(vector<vi> _p) {
	p = _p;
	_p.clear();

	n = sz(p);

	for(int i = 0; i < n; i++){
		if(p[i][i] != 1) return 0; 
		for(int j = 0; j < n; j++){
			if(p[i][j] != p[j][i]) return 0;
			if(p[i][j] == 3) return 0;
		}
	}

	
	for(int i = 0; i < n; i++) {
		vi row(n, 0);
		ans.pb(row);
	}

	DSU dsu0;
	dsu0.init(n);

	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(p[i][j] > 0){
				dsu0.unite(i, j);
			}
		}
	}

	for(int i = 0; i < n; i++){
		comps[dsu0.get(i)].pb(i);
	}

	for(int i = 0; i < n; i++){
		if(sz(comps[i]) == 0) continue;
		int res = solve(comps[i]);
		if(res == 0) return 0;
	}

	build(ans);
	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