Submission #625339

#	Time	Username	Problem	Language	Result	Execution time	Memory
625339		OrazB	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	282 ms	27508 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define N 1005
#define wr cout << "Continue debugging\n";
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
using namespace std;

int col[N], p[N][N], k[N], m[N];
vector <int> e[N];
vector<vector<int>> b;

int construct (vector <vector<int>> p){
	int cnt = 0;
	int n = p.size();
	b.resize(n);
	for (int i = 0; i < (int)p.size(); i++){
		b[i].resize(n);
		for (int j = 0; j < (int)(int)p[i].size(); j++) if (p[i][j] != p[j][i]) return 0;
	}
	for (int i = 0; i < (int)p.size(); i++){
		if (!col[i]) cnt++, col[i] = cnt;
		for (int j = 0; j < (int)p[i].size(); j++){
			if (!p[i][j]) continue; 
			col[j] = col[i];
			if (p[i][j] != 1 and k[col[i]] and k[col[i]] != p[i][j]) return 0;
			else if (p[i][j] != 1) k[col[i]] = p[i][j];
		}
	}
	for (int i = 0; i < (int)p.size(); i++) if (!k[col[i]]) k[col[i]] = 1;
	for (int i = 0; i < (int)p.size(); i++){
		cnt = 0;
		for (int j = 0; j < (int)p[i].size(); j++) if (p[i][j] == k[col[i]]) cnt++;
		if (cnt < k[col[i]]) return 0;
	}
	cnt = 0;
	for (int i = 0; i < (int)p.size(); i++){
		if (m[i]){
			for (int j = 0; j < (int)p[i].size(); j++) if (e[m[i]][j] != p[i][j]) return 0;
			continue;
		}
		cnt++;
		for (int j = 0; j < (int)p[i].size(); j++) e[cnt].pb(p[i][j]);
		for (int j = 0; j < (int)p[i].size(); j++){
			if (i == j or p[i][j] != 1 or m[j]) continue;
			b[i][j] = b[j][i] = 1; m[j] = cnt;
		}
	}
	for (int i = 0; i < (int)p.size(); i++){
		if (m[i]) continue;
		for (int j = 0; j < (int)p[i].size(); j++){
			if (p[i][j] < 2 or m[j]) continue;
			b[i][j] = b[j][i] = 1;
		}
	}
	build(b);
	// for (int i = 0; i < p.size(); i++){
	// 	for (int j = 0; j < p[i].size(); j++) cout << b[i][j] << " ";
	// 	cout << '\n';
	// }
	return 1;
}
// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n;
// 	cin >> n;
// 	vector<vector<int>> afk(n, vector <int> (n));
// 	for (int i = 0; i < n; i++){
// 		for (int j = 0; j < n; j++) cin >> afk[i][j];
// 	}
// 	cout << construct(afk);
// }	

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