Submission #603786

#	Time	Username	Problem	Language	Result	Execution time	Memory
603786		gagik_2007	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	200 ms	26128 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;

typedef long long ll;
typedef long double ld;

ll n, k;
vector<vector<int>>a, d;
vector<int>c, fst, lst, gic;
vector<bool>used, kagic;
vector<bool>mej;
const int INF = 1e9 + 7;

int construct(vector<vector<int>> p) {
	n = p.size();
	a = p;
	c.resize(n, INF);
	fst.resize(n, -1);
	lst.resize(n, -1);
	gic.resize(n, INF);
	d.resize(n);
	for (int i = 0; i < n; i++) {
		d[i].resize(n, 0);
	}
	used.resize(n, false);
	mej.resize(n, true);
	kagic.resize(n, false);
	bool ent1 = true;
	bool ent2 = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j] != 0 && p[i][j] != 1) {
				ent1 = false;
			}
			if (i != j && (p[i][j] != 0 && p[i][j] != 2)) {
				ent2 = false;
			}
		}
	}
	if (ent1) {
		int cur = 0;
		for (int v = 0; v < n; v++) {
			if (c[v] == INF) {
				c[v] = cur++;
			}
			for (int to = 0; to < n; to++) {
				if (p[v][to] == 1) {
					if (c[to] != INF && c[to] != c[v]) {
						return 0;
					}
					c[to] = c[v];
				}
				else {
					if (c[to] == c[v])return 0;
				}
			}
		}


		for (int v = 0; v < n; v++) {
			for (int to = v + 1; to < n; to++) {
				if (c[to] == c[v]) {
					d[v][to] = d[to][v] = 1;
					break;
				}
			}
		}
		build(d);
		return 1;
	}





	else if (ent2) {
		int cur = 0;
		for (int v = 0; v < n; v++) {
			if (c[v] == INF) {
				c[v] = cur++;
			}
			for (int to = 0; to < n; to++) {
				if (p[v][to] == 2) {
					if (c[to] != INF && c[to] != c[v]) {
						return 0;
					}
					c[to] = c[v];
				}
				else if (p[v][to] == 0) {
					if (c[to] == c[v])return 0;
				}
			}
		}


		for (int v = 0; v < n; v++) {
			bool ok = false;
			if (fst[c[v]] == -1) {
				fst[c[v]] = v;
			}
			for (int to = v + 1; to < n; to++) {
				if (c[to] == c[v]) {
					d[v][to] = d[to][v] = 1;
					ok = true;
					break;
				}
			}
			if (!ok) {
				int to = fst[c[v]];
				if (to != v) {
					if (d[to][v] == 1)return 0;
					d[to][v] = d[v][to] = 1;
				}
			}
		}
		build(d);
		return 1;
	}





	else {
		int cur = 0;
		for (int v = 0; v < n; v++) {
			if (c[v] == INF) {
				c[v] = cur++;
			}
			for (int to = 0; to < n; to++) {
				if (p[v][to] == 2 || p[v][to] == 1) {
					if (c[to] != INF && c[to] != c[v]) {
						return 0;
					}
					c[to] = c[v];
				}
				else if (p[v][to] == 0) {
					if (c[to] == c[v])return 0;
				}
			}
		}


		for (int v = 0; v < n; v++) {
			for (int to = 0; to < n; to++) {
				if (to != v && p[v][to] == 1) {
					mej[v] = false;
					break;
				}
			}
		}


		for (int v = 0; v < n; v++) {
			if (mej[v]) {
				//cout << "Cikli mej a: " << v << endl;
				used[v] = true;
				if (fst[c[v]] == -1) {
					fst[c[v]] = v;
				}
				lst[c[v]] = v;
				for (int to = v + 1; to < n; to++) {
					if (c[to] == c[v] && mej[to]) {
						d[v][to] = d[to][v] = 1;
						//cout << "Kpan1: " << v << " " << to << endl;
						break;
					}
				}
			}
		}

		int curgic = 0;
		for (int v = 0; v < n; v++) {
			if (!used[v]) {
				if (gic[v] == INF) {
					gic[v] = curgic++;
				}
				kagic[c[v]] = true;
				for (int to = 0; to < n; to++) {
					if (p[v][to] == 1) {
						if (gic[to] != INF && gic[to] != gic[v]) {
							return 0;
						}
						gic[to] = gic[v];
					}
					else if (p[v][to] == 2 && gic[to] == gic[v]) {
						return 0;
					}
				}
			}
		}


		for (int v = 0; v < n; v++) {
			if (!used[v]) {
				bool ok = false;
				for (int to = v + 1; to < n; to++) {
					if (c[to] == c[v] && gic[to] == gic[v]) {
						d[v][to] = d[to][v] = 1;
						//cout << "Kpan2: " << v << " " << to << endl;
						ok = true;
						break;
					}
				}
				if (!ok) {
					//cout << "Verjiny " << c[v] << " guyni " << gic[v] << " toxi: " << v << endl;
					int to = fst[c[v]];
					if (to != v && to != -1) {
						if (d[to][v] == 1)return 0;
						d[to][v] = d[v][to] = 1;
						//cout << "Kpan3: " << v << " " << to << endl;
					}
					to = lst[c[v]];
					if (to != v && to != -1 && to != fst[c[v]]) {
						if (d[to][v] == 1)return 0;
						d[to][v] = d[v][to] = 1;
						//cout << "Kpan4: " << v << " " << to << endl;
					}
					if (lst[c[v]] == -1) {
						lst[c[v]] = v;
					}
					else fst[c[v]] = v;
				}
				////cout << v << endl;
			}
		}
		for (int i = 0; i < n; i++) {
			if (!kagic[i]) {
				if (fst[i] == lst[i])continue;
				if (d[fst[i]][lst[i]])return 0;
				d[fst[i]][lst[i]] = d[lst[i]][fst[i]] = 1;
			}
		}
		//return 1;
		//cout << "3: " << c[3] << " " << gic[3] << " " << used[3] << endl;
		build(d);
		return 1;
	}
}

/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

6 
1 1 2 2 2 2 
1 1 2 2 2 2 
2 2 1 2 2 1 
2 2 2 1 1 2 
2 2 2 1 1 2 
2 2 1 2 2 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