Submission #823017

#	Time	Username	Problem	Language	Result	Execution time	Memory
823017		fatemetmhr	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	207 ms	26028 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);
	}
}

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();
		tp.clear();
		dfs0(i);
		int mx = 0, cnt2 = 0;
		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;
			mx = max(mx, a[ver[j]][ver[k]]);
			cnt2 += (a[ver[j]][ver[k]] == 2);
		}
		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);
		}
		if(tp.size() == 2)
			return 0;
		if(mx == 3 && (tp.size() != 4 || cnt2 > 0))
			return 0;
		if(mx == 3){
			int a = tp[0], b = tp[1], c = tp[2], d = tp[3];
			ret[a][b] = ret[b][a] = 1;
			ret[b][c] = ret[c][b] = 1;
			ret[c][d] = ret[d][c] = 1;
			ret[d][a] = ret[a][d] = 1;
			ret[a][c] = ret[c][a] = 1;
		}
		else{
			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:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0; j < ver.size(); j++) for(int k = 0; k < ver.size(); k++){
      |                  ~~^~~~~~~~~~~~
supertrees.cpp:55:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0; j < ver.size(); j++) for(int k = 0; k < ver.size(); k++){
      |                                                      ~~^~~~~~~~~~~~
supertrees.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(int i = 0; i < av.size(); i++) for(int j = 0; j < av.size(); j++)
      |                   ~~^~~~~~~~~~~
supertrees.cpp:64:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(int i = 0; i < av.size(); i++) for(int j = 0; j < av.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