Submission #822997

#	Time	Username	Problem	Language	Result	Execution time	Memory
822997		fatemetmhr	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	177 ms	26040 KiB

supertrees

// :)

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

using namespace std;

#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
#define mp     make_pair
#define pb     push_back

typedef long long ll;


const int maxn5 = 1e3 + 10;

vector<vector<int>> ret;
vector <int> tp, av, ver;
bool mark[maxn5], mark2[maxn5];
int n, a[maxn5][maxn5];

void dfs0(int v){
	mark[v] = true;
	ver.pb(v);
	for(int i = 0; i < n; i++) if(a[v][i] > 0 && !mark[i])
		dfs0(i);
}

void dfs1(int v){
	mark2[v] = true;
	av.pb(v);
	for(int i = 0; i < n; i++) if(a[v][i] == 1 && !mark2[i]){
		ret[v][i] = ret[i][v] = 1;
		dfs1(i);
		return;
	}
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	for (int i = 0; i < n; i++){
		vector<int> row;
		row.resize(n);
		fill(all(row), 0);
		ret.push_back(row);
		for(int j = 0; j < n; j++)
			a[i][j] = p[i][j];
	}
	for(int i = 0; i < n; i++) if(!mark[i]){
		ver.clear();
		for(int j = 0; j < ver.size(); j++) for(int k = 0; k < ver.size(); k++)
			if(a[ver[j]][ver[k]] == 0)
				return 0;
		tp.clear();
		dfs0(i);
		for(auto u : ver) if(!mark2[u]){
			av.clear();
			dfs1(u);
			for(int i = 0; i < av.size(); i++) for(int j = 0; j < av.size(); j++)
				if(a[av[i]][av[j]] != 1)
					return 0;
			tp.pb(u);
		}
		for(int i = 1; i < int(tp.size()); i++)
			ret[tp[i]][tp[i - 1]] = ret[tp[i - 1]][tp[i]] = 1;
		if(tp.size() > 1)
			ret[tp.back()][tp[0]] = ret[tp[0]][tp.back()] = 1;
	}
	build(ret);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j = 0; j < ver.size(); j++) for(int k = 0; k < ver.size(); k++)
      |                  ~~^~~~~~~~~~~~
supertrees.cpp:53:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j = 0; j < ver.size(); j++) for(int k = 0; k < ver.size(); k++)
      |                                                      ~~^~~~~~~~~~~~
supertrees.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int i = 0; i < av.size(); i++) for(int j = 0; j < av.size(); j++)
      |                   ~~^~~~~~~~~~~
supertrees.cpp:61:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int i = 0; i < av.size(); i++) for(int j = 0; j < av.size(); j++)
      |                                                      ~~^~~~~~~~~~~

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