Submission #316363

#	Time	Username	Problem	Language	Result	Execution time	Memory
316363		tigicha	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	291 ms	34168 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int par[1005], ar[1005], a[1005][1005], ans[1005][1005], fix1[1005], n, fix[1005];
vector<int> V[1005], vec[1005], v1;
vector<vector<int> > answer;
int parent(int x){
	if(par[x]==x) return x;
	return par[x]=parent(par[x]);
}
void dsu(int x, int y){
	x=parent(x);
	y=parent(y);
	if(x==y) return;
	if(ar[x]<ar[y]) swap(x, y);
	par[y]=x;
	ar[x]+=ar[y];
}
void rec(int x){
	for(int i=0; i<V[x].size(); i++)
	for(int j=i+1; j<V[x].size(); j++)
	if(a[V[x][i]][V[x][j]]==1){
	vec[V[x][i]].push_back(V[x][j]);
	vec[V[x][j]].push_back(V[x][i]);
	}
	v1.clear();
	for(int i=0; i<V[x].size(); i++){
		int y=V[x][i]; 
		if(fix[y]) continue;
		v1.push_back(y);
		fix1[y]=1;
		if(!fix[y])
		for(int j=0; j<vec[y].size(); j++){
			fix[vec[y][j]]=y;
			ans[y][vec[y][j]]=ans[vec[y][j]][y]=1;
		}
	}
	if(v1.size()>1)
	for(int i=0; i<v1.size(); i++)
	ans[v1[i]][v1[(i+1)%v1.size()]]=ans[v1[(i+1)%v1.size()]][v1[i]]=1;
}
bool check(){
	for(int i=1; i<=n; i++){
		std::vector<int> vec1;
		for(int j=1; j<=n; j++){
			if(i==j) ans[i][j]=0;
			else{
				int x=parent(i);
				int y=parent(j);
				if(a[i][j]==0 && parent(i)==parent(j)) return 0;
				if(!fix1[i] && !fix1[j] && a[i][j]==2 && fix[i]==fix[j]) return 0;
			}
			vec1.push_back(ans[i][j]); 
		}
		answer.push_back(vec1);
	}
	return 1;
}
int construct(std::vector<std::vector<int> > v){
	n=v.size(); 
	for(int i=1; i<=n; i++){
		par[i]=i;
		ar[i]=1;
	}
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++){
		a[i][j]=v[i-1][j-1];
		if(a[i][j]==3)  return 0;	
		if(a[i][j]!=0) dsu(i, j);
	}
	for(int i=1; i<=n; i++)
	V[parent(i)].push_back(i);
	for(int i=1; i<=n; i++){
		rec(i);
		if(v1.size()==2 && a[v1[0]][v1[1]]==2) return 0;
	}
	if(!check()) return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void rec(int)':
supertrees.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<V[x].size(); i++)
      |               ~^~~~~~~~~~~~
supertrees.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int j=i+1; j<V[x].size(); j++)
      |                 ~^~~~~~~~~~~~
supertrees.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0; i<V[x].size(); i++){
      |               ~^~~~~~~~~~~~
supertrees.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j=0; j<vec[y].size(); j++){
      |                ~^~~~~~~~~~~~~~
supertrees.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0; i<v1.size(); i++)
      |               ~^~~~~~~~~~
supertrees.cpp: In function 'bool check()':
supertrees.cpp:48:9: warning: unused variable 'x' [-Wunused-variable]
   48 |     int x=parent(i);
      |         ^
supertrees.cpp:49:9: warning: unused variable 'y' [-Wunused-variable]
   49 |     int y=parent(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