Submission #565744

#	Time	Username	Problem	Language	Result	Execution time	Memory
565744		sidon	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	255 ms	24012 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;

int construct(vector<vector<int>> p) {
	int n = size(p);
	vector<vector<int>> g(n, vector<int> (n));
	bool vis[n] {};

	for(int r = 0; r < n; ++r) if(!vis[r]) {
		vector<int> c;
		vector<vector<int>> s;

		for(int i = r; i < n; ++i) if(!vis[i] && p[r][i]) {
			vis[i] = 1;
			c.push_back(i);
		}

		for(int i : c) {
			for(int j : c) if(!p[i][j]) return 0;

			if(vis[i]) {
				s.push_back({});
				for(int j : c) if(p[i][j] < 2 && vis[j]) {
					vis[j] = 0;
					s.back().push_back(j);
				} 
			}
		}
		for(auto &x : s) {
			for(auto &y : s) for(int i : x) for(int j : y)
				if((x[0] != y[0]) != (p[i][j] > 1)) return 0;

			for(int i = 1; i < int(size(x)); ++i)
				g[x[i-1]][x[i]] = g[x[i]][x[i-1]] = 1;
		}
		if(size(s) == 2) return 0;
		for(int i = 0; i < int(size(s)); ++i) {
			int u = s[i][0], v = s[(i+1) % size(s)][0];
			if(u != v) g[u][v] = g[v][u] = 1;
		}
		for(int i : c) for(int j = 0; j < n; ++j)
			if(vis[j] && p[i][j]) return 0;

		for(int i : c) vis[i] = 1;
	}

	return build(g), 1;
}

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