Submission #603437

#	Time	Username	Problem	Language	Result	Execution time	Memory
603437		gagik_2007	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	215 ms	28000 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, lst;
const int INF = 1e9 + 7;

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

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