Submission #1239480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239480		Sir_Ahmed_Imran	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	119 ms	26536 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

bool po;
int cc[MAXN];
int par[MAXN];
int a[MAXN][MAXN];
vector<int> e[MAXN];
vector<vector<int>> ans;

void get(vector<int> v){
	if(!v.size()) return;
	vector<int> u, l;
	u.append(v.back());
	v.pop_back();
	bool c;
	cc[u[0]] = u[0];
	for(auto & i : v){
		if(a[i][u[0]] == 0){
			l.append(i);
			continue;
		}
		c = 1;
		cc[i] = u[0];
		for(auto & j : u){
			if(a[i][j] == 1){
				par[i] = j;
				c = 0;
				break;
			}
		}
		if(c) u.append(i);
	}
	int n = u.size();
	if(n == 2){
		po = 0;
		return;
	}
	if(n == 1) n = 0;
	for(int i = 0; i < n; i++){
		ans[u[i]][u[(i + 1) % n]] = 1;
		ans[u[(i + 1) % n]][u[i]] = 1;
	}
	get(l);
}

int construct(vector<vector<int>> p){
	int n = p[0].size();
	vector<int> v, u;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			a[i][j] = p[i][j];
			if(p[i][j] != p[j][i])
				return 0;
		}
		v.append(i);
		u.append(0);
		par[i] = i;
	}
	for(int i = 0; i < n; i++)
		ans.append(u);
	po = 1;
	get(v);
	if(!po) return 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(cc[i] != cc[j]){
				if(a[i][j] != 0)
					return 0;
			}
			else if(par[i] == par[j]){
				if(a[i][j] != 1){
					return 0;
				}
				if(i != par[i]){
					ans[i][par[i]] = 1;
					ans[par[i]][i] = 1;
				}
			}
			else if(a[i][j] != 2) 
				return 0;
		}
	}
	build(ans);
	return 1;
}

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