Submission #1218311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218311		brinton	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	135 ms	22272 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int construct(vector<vector<int>> p) {

	for(auto &i:p){
		for(auto &j:i){
			if(j == 3) return 0;
		}
	}
	int N = p.size();
	vector<vector<int>> answer(N,vector<int>(N,0));

	
	
	vector<int> gline(N,-1);
	for(int i = 0;i < N;i++) gline[i] = i;
	set<int> cs;
	function<void(int,int)> dfs = [&](int cur,int need){
		cs.insert(cur);
		for(int nxt = 0;nxt < N;nxt++){
			if(nxt == cur) continue;
			if(cs.count(nxt)) continue;
			if(p[nxt][cur] == need){
				dfs(nxt,need);
			}
		}
	};
	auto check = [&](vector<int> &v,int need){
		for(auto &i:v){
			for(auto &j:v){
				if(i == j) continue;
				if(p[i][j] != need) return false;
			}
		}
		return true;
	};
	for(int i = 0;i < N;i++){
		if(gline[i] != i) continue;
		cs.clear();
		dfs(i,1);
		if(cs.size() == 1) continue;
		vector<int> cv(cs.begin(),cs.end());
		if(!check(cv,1)) return 0;
		for(int i = 0;i +1 < cv.size();i++){
			answer[cv[i]][cv[i+1]] = 1;
		}
		for(auto &i:cv) gline[i] = cv[0];
	}
	// build cycle;
	vector<int> gcycle(N,-1);
	for(int i = 0;i < N;i++){
		if(gcycle[i] != -1) continue;
		cs.clear();
		dfs(i,2);
		vector<int> cv(cs.begin(),cs.end());

		set<int> sLine;
		for(auto &i:cv) sLine.insert(gline[i]);
		if(sLine.size() == 1) continue;
		if(sLine.size() <= 2) return 0;
		// check valid
		for(auto &i:cv){
			for(auto &j:cv){
				if(gline[i] != gline[j] && p[i][j] != 2) return 0;
			}
		}
		vector<int> vLine(sLine.begin(),sLine.end());
		for(int i = 0;i < vLine.size();i++){
			answer[vLine[i]][vLine[(i+1)%vLine.size()]] = 1;
		}
		for(auto &i:cv) gcycle[i] = cv[0];

	}

	// mirror;
	for(int i = 0;i < N;i++){
		for(int j = 0;j < N;j++){
			answer[i][j] |= answer[j][i];
			answer[j][i] |= answer[i][j];
		}
	}
	build(answer);
	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