Submission #1050083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050083		noyancanturk	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	113 ms	26196 KiB

supertrees

#include "supertrees.h"

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

const int lim=2000;

#define pb push_back

int n;
bool used[lim];
vector<vector<int>>comps,need,ans;

bool buildcomp(vector<int>&v){
	unordered_set<int>myguys;
	for(int i=0;i<v.size();i++){
		myguys.insert(v[i]);
	}
	for(int i=0;i<v.size();i++){
		for(int j=0;j<n;j++){
			if(need[v[i]][j]&&!myguys.count(j))return 0;
			if(!need[v[i]][j]&&myguys.count(j))return 0;
		}
	}
	vector<int>loop;
	vector<vector<int>>chains;
	for(int node:v){
		if(!used[node]){
			used[node]=1;
			chains.pb({});
			for(int i=0;i<n;i++){
				if(need[node][i]==1){
					chains.back().pb(i);
					used[i]=1;
				}
			}
		}
	}
	//verify chains
	for(auto&u:chains){
		for(int i=0;i<u.size();i++){
			for(int j=0;j<u.size();j++){
				if(need[u[i]][u[j]]!=1)return 0;
			}
		}
	}
	//verify all
	if(chains.size()==1){
		for(int i=0;i+1<chains[0].size();i++){
			ans[chains[0][i]][chains[0][i+1]]=ans[chains[0][i+1]][chains[0][i]]=1;
		}
		return 1;
	}
	if(chains.size()==2){
		return 0;
	}
	for(int i=0;i<chains.size();i++){
		auto&u=chains[i];
		for(int j=0;j+1<u.size();j++){
			ans[u[j]][u[j+1]]=ans[u[j+1]][u[j]]=1;
		}
		if(i)ans[u[0]][chains[i-1][0]]=ans[chains[i-1][0]][u[0]]=1;
		else ans[u[0]][chains.back()[0]]=ans[chains.back()[0]][u[0]]=1;
	}
	return 1;
}

int construct(std::vector<std::vector<int>> p) {
	need=p;
	n = p.size();
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==3)return 0;
		}
		if(!used[i]){
			comps.pb({});
			for(int j=0;j<n;j++){
				if(p[i][j]){
					if(used[j])return 0;
					comps.back().pb(j);
					used[j]=1;
				}
			}
		}
		ans.pb(vector<int>(n,0));
	}
	memset(used,0,n);
	for(int i=0;i<comps.size();i++){
		if(!buildcomp(comps[i])){
			return 0;
		}
	}
	build(ans);
	return 1;
}
/*
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	build(answer);
	return 1;
}
*/

Compilation message (stderr)

supertrees.cpp: In function 'bool buildcomp(std::vector<int>&)':
supertrees.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
supertrees.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
supertrees.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i=0;i<u.size();i++){
      |               ~^~~~~~~~~
supertrees.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int j=0;j<u.size();j++){
      |                ~^~~~~~~~~
supertrees.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i+1<chains[0].size();i++){
      |               ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<chains.size();i++){
      |              ~^~~~~~~~~~~~~~
supertrees.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int j=0;j+1<u.size();j++){
      |               ~~~^~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=0;i<comps.size();i++){
      |              ~^~~~~~~~~~~~~

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