Submission #300281

#	Time	Username	Problem	Language	Result	Execution time	Memory
300281		aljasdlas	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	279 ms	30200 KiB

supertrees

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

bool possible = true;
vector<vector<int>> b;
int n;
bitset<1005> vis;
bitset<1005> isOne;
vector<int> AdjList[1005];

vector<vector<int>> components;
int compNum[1005];
vector<vector<int>> p;

void dfs(int u) {
// << u << " ";
	vis[u] = 1;
	compNum[u] = components.size();
	components.back().push_back(u);
	for(auto &v: AdjList[u])
		if(!vis[v])
			dfs(v);
}


int construct(vector<vector<int>> p_) {
	p = p_;
	n = p.size();
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(p[i][j] != 0)
				AdjList[i].push_back(j);

	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		b.push_back(row);
	}

	vis.reset();

	for(int i = 0; i < n; i++)
		if(!vis[i]) {
			components.push_back(vector<int>(0));
		// << "Comp " << components.size() << ": ";
			dfs(i);
		// << endl;
		}

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(compNum[i] == compNum[j] && p[i][j] == 0)
				return 0;
			else if(compNum[i] != compNum[j] && p[i][j] > 0)
				return 0;

	for(auto &v: components) {
		isOne.reset();
		if(v.size() == 1)
			continue;
		for(auto &x: v) {
			for(auto &y: v) {
				if(x == y) continue;
				if(p[x][y] == 1)
					isOne[x]=isOne[y]=1;
			}
		}

		for(auto &x: v) {
			for(auto &y: v) {
				if(x == y) continue;
				if(isOne[x]) {
					if(isOne[y]) {
						if(p[x][y] != 1) return 0;
					}
				}
			}
		}

		vector<int> is[3];
		for(auto &x: v)
			if(isOne[x]) is[1].push_back(x);
			else is[2].push_back(x);
		
		
	// << "Is 1: "; for(auto x: is[1]) cerr << x << " "; cerr << endl;
	// << "Is 2: "; for(auto x: is[2]) cerr << x << " "; cerr << endl;

		if(is[2].size() == 1) return 0;
		if(is[2].size() == 0) {
			for(int i = 1; i < is[1].size(); i++) {
				b[is[1][i-1]][is[1][i]] = 1;
				b[is[1][i]][is[1][i-1]] = 1;
			}
		} else if(is[1].size() == 0) {
			for(int i = 1; i < is[2].size(); i++) {
				b[is[2][i-1]][is[2][i]] = 1;
				b[is[2][i]][is[2][i-1]] = 1;
			}
			b[is[2][is[2].size()-1]][is[2][0]] = 1;
			b[is[2][0]][is[2][is[2].size()-1]] = 1;
			if(is[2].size() == 2) return 0;
		} else {
			for(int i = 1; i < is[1].size(); i++) {
				b[is[1][i-1]][is[1][i]] = 1;
				b[is[1][i]][is[1][i-1]] = 1;
			}
			for(int i = 1; i < is[2].size(); i++) {
				b[is[2][i-1]][is[2][i]] = 1;
				b[is[2][i]][is[2][i-1]] = 1;
			}
			b[is[2][0]][is[1][is[1].size()-1]] = 1;
			b[is[1][is[1].size()-1]][is[2][0]] = 1;
			b[is[2][is[2].size()-1]][is[1][is[1].size()-1]] = 1;
			b[is[1][is[1].size()-1]][is[2][is[2].size()-1]] = 1;
		}
	}

	if(!possible)
		return 0;
	
	build(b);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i = 1; i < is[1].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for(int i = 1; i < is[2].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for(int i = 1; i < is[1].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    for(int i = 1; i < is[2].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~

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