Submission #300453

#	Time	Username	Problem	Language	Result	Execution time	Memory
300453		mohammad	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	314 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll ;

int root[1020] , de[1020] , use[1020] , r[1020];

ll find(int u){
	if(root[u] == u) return u;
	return root[u] = find(root[u]);
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n , vector<int>(n , 0));
	for(int i = 0 ; i < n ; ++i){
		if(p[i][i] != 1) return 0 ;
		root[i] = i ; 
	}
	for(int i = 0 ; i < n; ++i)
		for(int j = 0 ; j < n; ++j){
			if(!p[i][j]) continue ;
			if(p[i][j] == 2 || p[i][j] == 0) r[i]++ ;
			root[find(i)] = find(j);
		}
	for(int i = 0 ; i < n ; ++i) {
		if(r[i] == n - 1) de[i] = 1;
		else de[i] = 0 ;
		find(i);
	}
	set<int> s[1020][3];
	for(int i = 0 ; i < n; ++i)
		for(int j = i + 1 ; j < n; ++j){
			if(p[i][j] == 0 && root[i] == root[j]) return 0 ;
			else if(p[i][j]){
				s[root[i]][de[i]].insert(i);
				s[root[i]][de[j]].insert(j);
			}
		}
	for(int i = 0 ; i < n; ++i){
		if(use[root[i]]) continue;
		use[root[i]] = 1;
		int ls = -1;
		if(!s[root[i]][1].size()){
			for(auto j : s[root[i]][0]){
				if(ls != -1){
					answer[ls][j] = 1;answer[j][ls] = 1;
				}else ls = j ;
			}
		}else if(!s[root[i]][0].size()){
			if(s[root[i]][1].size() <= 2) return 0;
			auto it = s[root[i]][1].begin();
			auto it1 = s[root[i]][1].begin(); it1++;
			auto it2 = s[root[i]][1].begin(); it2++;it2++;
			answer[*it][*it1] = 1;answer[*it1][*it] = 1;
			for(; it2 != s[root[i]][1].end(); it2++ , it1++){
				answer[*it2][*it1] = 1;answer[*it1][*it2] = 1;
			}
			answer[*it][*it1] = 1;answer[*it1][*it] = 1;
		}else{
			return 0;
			if(s[root[i]][1].size() <= 1) return 0;
			for(auto j : s[root[i]][0]){
				if(ls != -1){
					answer[ls][j] = 1;answer[j][ls] = 1;
				}else ls = j ;
			}
			int it = ls;
			auto it1 = s[root[i]][1].begin();
			auto it2 = s[root[i]][1].begin(); it2++;
			answer[it][*it1] = 1;answer[*it1][it] = 1;
			for(; it2 != s[root[i]][1].end(); it2++ , it1++){
				answer[*it2][*it1] = 1;answer[*it1][*it2] = 1;
			}
			answer[it][*it1] = 1;answer[*it1][it] = 1;
		}
	}
	build(answer);
	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