Submission #897817

#	Time	Username	Problem	Language	Result	Execution time	Memory
897817		aqxa	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	180 ms	24324 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long; 

const int N = 1001; 

#include "supertrees.h"
// void build(vector<vector<int>> g) {
// 	int n = g.size(); 
// 	for (int i = 0; i < n; ++i) {
// 		for (int j = 0; j < n; ++j) cout << g[i][j]; 
// 		cout << "\n";
// 	}
// }

int construct(vector<std::vector<int>> p) {
	int n = p.size();

	vector<int> vis(n, 0);  
	int cnt = 0; 

	vector<vector<int>> comp; 

	for (int i = 0;	i < n; ++i) {
		if (!vis[i]) {
			vis[i] = ++cnt; 
			vector<int> cur(1, i); 
			queue<int> q; 
			q.push(i); 
			while (!q.empty()) {
				auto x = q.front(); 
				q.pop(); 
				for (int u = 0; u < n; ++u) { 
					if (u != x && p[x][u] > 0 && vis[u] == 0) {
						vis[u] = cnt; 
						q.push(u); 
						cur.push_back(u); 
					}
				}
			}

			comp.push_back(cur); 
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 3) return 0; 
			if (p[i][j] == 0 && vis[i] == vis[j]) return 0; 
			if (p[i][j] > 0 && vis[i] != vis[j]) return 0; 
		}
	}

	vector<vector<int>> ans(n, vector<int>(n, 0)); 
	for (int i = 0; i < n; ++i) ans[i][i] = 0; 

	for (auto c: comp) {
		int m = c.size(); 
		vector<int> vis2(m, 0); 
		int cnt2 = 0;  
		vector<vector<int>> comp2; 
		for (int i = 0; i < m; ++i) {
			if (!vis2[i]) {
				vis2[i] = ++cnt2; 
				vector<int> cur(1, i); 
				queue<int> q; 
				q.push(i); 
				while (!q.empty()) {
					auto x = q.front(); 
					q.pop(); 
					for (int u = 0; u < m; ++u) {
						if (u != x && p[c[x]][c[u]] == 1 && vis2[u] == 0) {
							vis2[u] = cnt2; 
							q.push(u); 
							cur.push_back(u); 
						}
					}
				}
				comp2.push_back(cur); 
			}
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < m; ++j) {
				if (vis2[i] == vis2[j] && p[c[i]][c[j]] != 1) return 0; 
				if (vis2[i] != vis2[j] && p[c[i]][c[j]] != 2) return 0; 
			}
		}
		if (comp2.size() == 2) return 0; 
		if (comp2.size() == 1) {
			for (int i = 0; i < m - 1; ++i) {
				ans[c[i]][c[i + 1]] = 1; 
				ans[c[i + 1]][c[i]] = 1; 
			}
		} else {
			for (int i = 0; i < (int) comp2.size(); ++i) {
				int u = comp2[i][0], v = comp2[(i + 1) % ((int) comp2.size())][0]; 
				ans[c[u]][c[v]] = 1; 
				ans[c[v]][c[u]] = 1; 

				for (int j = 1; j < (int) comp2[i].size(); ++j) {
					ans[c[u]][c[comp2[i][j]]] = 1; 
					ans[c[comp2[i][j]]][c[u]] = 1; 
				}
			}
		}
	}
	build(ans); 

	return 1;
}

 
// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
	
// 	int n; 
// 	cin >> n; 
// 	vector<vector<int>> g(n, vector<int>(n)); 
// 	for (auto & x: g) for (auto & y: x) cin >> y; 
// 	cout << "Ans: \n" << construct(g) << "\n";

 
// 	return 0; 
// }	 

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