Submission #1318542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318542		Ekber_Ekber	Connecting Supertrees (IOI20_supertrees)	C++20	46 / 100	101 ms	26108 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
int n;
vector <vector <int>> res;

struct DSU{
	int n;
	vector <int> par;
	void init(int n1) {
		n = n1;
		par.assign(n+1, -1);
	}
	int get(int u) {
		if (par[u] < 0) return u;
		return par[u] = get(par[u]);
	}
	bool un(int a, int b) {
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if (par[a] < par[b]) swap(a, b);
		par[b] += par[a];
		par[a] = b;
		return 1;
	}
};

int construct(vector<vector<int>> p) {
	n = p.size();
	
	res.assign(n, vector <int>(n, 0));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] == 3) return 0;
		}
	}

	vector <pair<vector <int>, vector <int>>> g(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!p[i][j] || i == j) continue;
			if (p[i][j] == 1) g[i].ff.pb(j);
			else g[i].ss.pb(j);
		}
	}

	DSU dsu;
	dsu.init(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j]) dsu.un(i, j);
		}
	}
	vector <vector <int>> cmp;
	vector <int> is(n, -1);
	for (int i = 0; i < n; i++) {
		int c = dsu.get(i);
		if (is[c] == -1) {
			is[c] = cmp.size();
			cmp.pb({});
		}
		is[i] = is[c];
	}
	for (int i = 0; i < n; i++) cmp[is[i]].pb(i);

	// cerr << "Components built:\n";
	// // for (auto &i : cmp) for (int &j : i) cerr << j << ' '; cerr << endl;
	// cerr << endl;

	vector <int> col(n, 0);
	for (auto &i : cmp) {
		vector <vector <int>> ch;
		for (int &j : i) {
			if (col[j]) continue;
			ch.pb({j});
			col[j] = 1;
			for (int &z : g[j].ff) {
				if (col[z]) return 0;
				ch.back().pb(z), col[z] = 1;
			}
		}
		// cerr << "\nAll chains in [ ";
		// for (int &j : i) cerr << j << ' ';
		// cerr << "] built:\n";
		// // for (auto &j : ch) for (int &z : j) cerr << z << ' '; cerr << endl;
		// cerr << endl;
		for (auto &j : ch) {
			for (int z = 1; z < j.size(); z++) res[j[z]][j[z-1]] = 1, res[j[z-1]][j[z]] = 1;
		}
		if (ch.size() == 1) continue;
		for (int j = 0; j < ch.size(); j++) {
			int z = (j + 1) % ch.size();
			int a = ch[j][0], b = ch[z][0];
			res[a][b] = 1;
			res[b][a] = 1;
		}
	}
	// cerr << "\n\nResult vector:\n";
	// // for (auto &i : res) for (int &j : i) cerr << j; cerr << endl;
	build(res);
	return 1;
}

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