Submission #603793

#	Time	Username	Problem	Language	Result	Execution time	Memory
603793		gagik_2007	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	226 ms	26072 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;
			}
		}
	}
	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;
				}
				if (lst[c[v]] == -1) {
					lst[c[v]] = v;
				}
				fst[c[v]] = v;
			}
			////cout << v << endl;
		}
	}
	for (int i = 0; i < n; 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
*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:34:7: warning: variable 'ent1' set but not used [-Wunused-but-set-variable]
   34 |  bool ent1 = true;
      |       ^~~~
supertrees.cpp:35:7: warning: variable 'ent2' set but not used [-Wunused-but-set-variable]
   35 |  bool ent2 = true;
      |       ^~~~

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