제출 #1218299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218299		brinton	Connecting Supertrees (IOI20_supertrees)	C++20	19 / 100	137 ms	22164 KiB

supertrees

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

int construct(vector<vector<int>> p) {
	int N = p.size();
	vector<vector<int>> answer(N,vector<int>(N,0));

	
	// build cycle;
	int gt = 0;
	vector<int> group(N,-1);
	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] == 2){
				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(group[i] != -1) continue;
		cs.clear();
		dfs(i,2);
		if(cs.size() == 1) continue;
		if(cs.size() == 2) return 0;
		
		if(cs.size() > 2){
			// build a cycle;
			vector<int> cv(cs.begin(),cs.end());
			if(!check(cv,2)){
				return 0;
			}
			for(auto i:cv) group[i] = gt;
			gt++;
			for(int i = 0;i < cv.size();i++){
				answer[cv[i]][cv[(i+1)%cv.size()]] = 1;
			}
		}
	}




	// 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: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4