Submission #314310

#	Time	Username	Problem	Language	Result	Execution time	Memory
314310		wildturtle	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	290 ms	45728 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int a,B[500005],B1[500005];
vector <int> v[500005],v1[500005],v2;
int get_col(int x) {
	if(B[x]==x) return x;
	B[x]=get_col(B[x]);
	return B[x];
}
void col(int x,int y) {
	B[get_col(x)]=get_col(y);
}
int get_col1(int x) {
	if(B1[x]==x) return x;
	B1[x]=get_col1(B1[x]);
	return B1[x];
}
void col1(int x,int y) {
	B1[get_col1(x)]=get_col1(y);
}
int construct(vector < vector < int > > p) {
	int n = p.size();
    vector < vector < int > > answer(n, vector < int >(n, 0));
	for (int i = 0; i < n; i++) {
		B[i]=i;
		B1[i]=i;
		for(int j=0;j<n;j++) {
			if(p[i][j]==3) return 0;
		}
	}

	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(p[i][j]!=0) col(i,j);
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(get_col(i)==get_col(j) && p[i][j]==0) return 0;
		}
	}
	
	for(int i=0;i<n;i++) {
		v[get_col(i)].push_back(i);
	}
	
	for(int i=0;i<n;i++) {
		if(v[i].size()==0) continue;
		a=0;
		for(int j=0;j<v[i].size();j++) {
			for(int l=0;l<v[i].size();l++) {
				if(p[v[i][j]][v[i][l]]==2) a=1;
				else col1(v[i][j],v[i][l]);
			}
		}
		
		if(a==0) {
			for(int j=1;j<v[i].size();j++) {
				answer[v[i][j-1]][v[i][j]]=1;
				answer[v[i][j]][v[i][j-1]]=1;
			}
			
		}
		else {
			for(int i=0;i<v[i].size();i++) {
				for(int j=0;j<v[i].size();j++) {
					if(get_col1(i)==get_col1(j) && p[i][j]==2) return 0;
				}
			}
			for(int j=0;j<v[i].size();j++)
				v1[get_col1(v[i][j])].push_back(v[i][j]);
			v2.clear();
			for(int j=0;j<v[i].size();j++) {
				if(v1[v[i][j]].size()==0) continue;
				v2.push_back(v1[v[i][j]][0]);
				for(int l=1;l<v1[v[i][j]].size();l++) {
					answer[v1[v[i][j]][l-1]][v1[v[i][j]][l]]=1;
					answer[v1[v[i][j]][l]][v1[v[i][j]][l-1]]=1;
				}
			}
			if(v2.size()==2) return 0;
			for(int j=0;j<v2.size();j++) {
				if(j==v2.size()-1) {
					answer[v2[0]][v2[j]]=1;
					answer[v2[j]][v2[0]]=1;
				}
				else {
					answer[v2[j+1]][v2[j]]=1;
					answer[v2[j]][v2[j+1]]=1;
				}
			}
			for(int j=0;j<v[i].size();j++)
				v1[get_col1(v[i][j])].clear();
		}
	}
	build(answer);
	/*for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cout<<answer[i][j]<<" ";
		}
		cout<<endl;
	}*/
	return 1;
}/*
int main() {
	//cout<<construct({ {1,0} , {0,1} });
	cout<<construct({ {1,1,2,2} , {1,1,2,2} , {2,2,1,2} , {2,2,2,1} });
	//1,1,2,2
	//1,1,2,2
	//2,2,1,2
	//2,2,2,1
}*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j=0;j<v[i].size();j++) {
      |               ~^~~~~~~~~~~~
supertrees.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int l=0;l<v[i].size();l++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:59:17: 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=1;j<v[i].size();j++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int i=0;i<v[i].size();i++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int j=0;j<v[i].size();j++) {
      |                 ~^~~~~~~~~~~~
supertrees.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int j=0;j<v[i].size();j++)
      |                ~^~~~~~~~~~~~
supertrees.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int j=0;j<v[i].size();j++) {
      |                ~^~~~~~~~~~~~
supertrees.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int l=1;l<v1[v[i][j]].size();l++) {
      |                 ~^~~~~~~~~~~~~~~~~~~
supertrees.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int j=0;j<v2.size();j++) {
      |                ~^~~~~~~~~~
supertrees.cpp:84:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if(j==v2.size()-1) {
      |        ~^~~~~~~~~~~~~
supertrees.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for(int j=0;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