Submission #1239476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239476		Sir_Ahmed_Imran	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	121 ms	26640 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];
bool vis[MAXN];
int a[MAXN][MAXN];
vector<int> e[MAXN];
vector<vector<int>> ans;

void get(vector<int> v){
	if(!v.size()) return;
	bool c;
	vector<int> u, t, l;
	for(auto & i : v){
		c = 1;
		vis[i] = 0;
		for(auto & j : u){
			if(a[i][j] == 0){
				if(j != u[0]){
					po = 0;
					return;
				}
				l.append(i);
				vis[i] = 1;
				c = 0;
			}
			if(a[i][j] == 1){
				t.append(i);
				par[i] = j;
				cc[i] = u[0];
				c = 0;
			}
		}
		if(c){
			t.append(i);
			u.append(i);
			par[i] = i;
			cc[i] = u[0];
		}
	}
	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);
	}
	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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4