제출 #1218307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218307		brinton	슈퍼트리 잇기 (IOI20_supertrees)	C++20	21 / 100	133 ms	22284 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));

	
	
	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;


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