Submission #603460

#	Time	Username	Problem	Language	Result	Execution time	Memory
603460		gagik_2007	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	237 ms	28036 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;
const int INF = 1e9 + 7;

int construct(vector<vector<int>> p) {
	n = p.size();
	a = p;
	c.resize(n, INF);
	fst.resize(n, -1);
	d.resize(n);
	for (int i = 0; i < n; i++) {
		d[i].resize(n, 0);
	}
	bool ent1 = 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 (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 {
		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;
	}
}

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