제출 #414550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414550		InternetPerson10	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	251 ms	24064 KiB

supertrees

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

using namespace std;

bool taken[1001];
int nums[1001], cycs[1001];

vector<vector<int>> paths;
vector<vector<int>> cycles;
vector<vector<int>> ans;

int construct(std::vector<std::vector<int>> p) {
	vector<vector<int>>().swap(paths);
	vector<vector<int>>().swap(cycles);
	vector<vector<int>>().swap(ans);
	int n = p.size();
	ans.resize(n);
	for(int i = 0; i < n; i++) {
		ans[i].resize(n);
		if(!taken[i]) {
			taken[i] = true;
			nums[i] = paths.size();
			paths.push_back(vector<int>());
			for(int j = i; j < n; j++) {
				if(p[i][j] == 1) {
					paths[nums[i]].push_back(j);
					taken[j] = true;
					nums[j] = nums[i];
				}
			}
		}
	}
	// for(int i = 0; i < n; i++) cout << nums[i] << ' ';
	// cout << '\n';
	for(int i = 0; i < n; i++) taken[i] = false;
	for(int i = 0; i < (int)paths.size(); i++) {
		if(!taken[i]) {
			taken[i] = true;
			cycles.push_back(vector<int>());
			cycles[cycles.size() - 1].push_back(i);
			cycs[i] = cycles.size() - 1;
			for(int j = i+1; j < (int)paths.size(); j++) {
				if(p[paths[i][0]][paths[j][0]] == 2) {
					taken[j] = true;
					cycles[cycles.size() - 1].push_back(j);
					cycs[j] = cycles.size() - 1;
				}
			}
		}
	}
	// cout << "yehey\n";
	// for(int i = 0; i < n; i++) cout << cycs[i] << ' ';
	// cout << '\n';
	bool sad = false;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			int pi = nums[i], pj = nums[j];
			int ci = cycs[pi], cj = cycs[pj];
			if(p[i][j] == 0) {
				if(pi == pj || ci == cj) sad = true;
			}
			else if(p[i][j] == 1) {
				if(pi != pj) sad = true;
			}
			else if(p[i][j] == 2) {
				if(pi == pj || ci != cj) sad = true;
			}
			else {
				sad = true;
			}
		}
	}
	for(int i = 0; i < (int)cycles.size(); i++) {
		if(cycles[i].size() == 2) sad = true;
	}
	if(sad) {
		return 0;
	}
	// cout << "Yehey\n";
	for(int i = 0; i < (int)paths.size(); i++) {
		for(int j = 1; j < (int)paths[i].size(); j++) {
			ans[paths[i][j]][paths[i][j-1]] = 1;
			ans[paths[i][j-1]][paths[i][j]] = 1;
		}
	}
	for(int i = 0; i < (int)cycles.size(); i++) {
		if(cycles[i].size() == 1) continue;
		ans[paths[cycles[i][0]][0]][paths[cycles[i][cycles[i].size() - 1]][0]] = 1;
		ans[paths[cycles[i][cycles[i].size() - 1]][0]][paths[cycles[i][0]][0]] = 1;
		for(int j = 1; j < (int)cycles[i].size(); j++) {
			ans[paths[cycles[i][j-1]][0]][paths[cycles[i][j]][0]] = 1;
			ans[paths[cycles[i][j]][0]][paths[cycles[i][j-1]][0]] = 1;
		}
	}
	build(ans);
	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