Submission #1178852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178852		the_coding_pooh	Connecting Supertrees (IOI20_supertrees)	C++20	56 / 100	128 ms	30212 KiB

supertrees

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

using namespace std;

const int SIZE = 1e3 + 5;

vector <int> graph[2][SIZE];

int answer[SIZE][SIZE];

bitset <SIZE> been;

int cc_head[SIZE], cc_cnt[SIZE];

vector <int> cc;

void get_cc(int nd, int tp){
	if(been[nd])
		return;
	been[nd] = 1;
	cc.push_back(nd);
	for(auto i:graph[tp][nd]){
		get_cc(i, tp);
	}
	return;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if(p[i][j])
				graph[p[i][j] - 1][i].push_back(j);
		}
	}
	for (int i = 0; i < n; i++){
		if(!been[i]){
			cc.clear();
			get_cc(i, 0);
			for(auto u:cc){
				cc_head[u] = i;
				for (auto v : cc){
					if(p[u][v] != 1)
						return 0;
				}
			}
			for (int j = 0; j + 1 < cc.size(); j++){
				answer[cc[j]][cc[j + 1]] = 1;
				answer[cc[j + 1]][cc[j]] = 1;
			}
			cc_cnt[i] = cc.size();
		}
	}
	been.reset();
	for (int i = 0; i < n; i++){
		if(!been[i] && !graph[1][i].empty()){
			cc.clear();
			get_cc(i, 1);
			set<int> st;
			for (auto u : cc){
				st.insert(cc_head[u]);
				for (auto v : cc){
					if(p[u][v] == 0)
						return 0;
				}
			}
			int tmp = 0;
			for (auto j : st){
				tmp += cc_cnt[j];
			}
			if(tmp != cc.size())
				return 0;
			for (auto j = st.begin(); next(j) != st.end(); j = next(j)){
				answer[*j][*next(j)] = 1;
				answer[*next(j)][*j] = 1;
			}
			if(st.size() >= 2){
				answer[*prev(st.end())][*st.begin()] = 1;
				answer[*st.begin()][*prev(st.end())] = 1;
			}
		}
	}
	vector<vector<int>> ret;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		for (int j = 0; j < n; j++){
			row.push_back(answer[i][j]);
		}
		ret.push_back(row);
	}
	build(ret);
	return 1;
}

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