Submission #1051390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051390		pcc	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	114 ms	26200 KiB

supertrees

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

const int mxn = 1010;

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
		fill(sz,sz+mxn,1);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
	}
};

/*
std::vector<std::vector<int>> answer(n,vector<int>(n,0));
build(answer);
return 1;
*/

DSU chain,cyc;
int N;
vector<vector<int>> ans;
vector<vector<int>> tar;
vector<int> v[mxn];
int head[mxn];

void add_edge(int a,int b){
	assert(a != b);
	ans[a][b] = ans[b][a] = 1;
}

bool check(){
	cerr<<"CHECK!"<<endl;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			if(i == j)continue;
			if(tar[i][j] == 0){
				if(chain.root(i) == chain.root(j))return false;
				int a = head[chain.root(i)],b = head[chain.root(j)];
				if(cyc.root(a) == cyc.root(b))return false;
			}
			else if(tar[i][j] == 1){
				if(chain.root(i) != chain.root(j))return false;
			}
			else{
				if(chain.root(i) == chain.root(j))return false;
				int a = head[chain.root(i)],b = head[chain.root(j)];
				if(cyc.root(a) != cyc.root(b))return false;
			}
		}
	}
	return true;
}


bitset<mxn> done;

bool CYCLE(){
	for(int i = 0;i<N;i++){
		if(done[i]||head[i] == -1)continue;
		cerr<<"CYC: "<<i<<endl;
		int now = head[i];
		vector<int> v;
		v.push_back(now);
		bool has = false;
		for(int j = 0;j<N;j++){
			if(tar[now][j] == 2){
				if(done[j])return false;
				has = true;
				v.push_back(head[chain.root(j)]);
			}
		}
		if(!has)continue;
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		if(v.size()<=2)return false;
		cerr<<now<<"::";for(auto &j:v)cerr<<j<<' ';cerr<<endl;
		for(int i = 1;i<v.size();i++){
			add_edge(v[i-1],v[i]);
			cyc.onion(v[i-1],v[i]);
		}
		add_edge(v[0],v.back());
		for(auto &i:v)done[chain.root(i)] = true;
	}
	return true;
}

int construct(std::vector<std::vector<int>> vvv) {
	memset(head,-1,sizeof(head));
	tar = vvv;
	N = tar.size();
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			if(tar[i][j] == 1)chain.onion(i,j);
		}
	}
	ans = vector<vector<int>>(N,vector<int>(N,0));
	for(int i = 0;i<N;i++){
		v[chain.root(i)].push_back(i);
	}
	for(int i = 0;i<N;i++){
		for(int j = 1;j<v[i].size();j++){
			add_edge(v[i][j-1],v[i][j]);
		}
		if(!v[i].empty())head[i] = v[i][0];
	}

	if(!CYCLE())return 0;

	if(!check())return 0;
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool CYCLE()':
supertrees.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int j = 1;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

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