Submission #1081469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081469		7mody	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	348 KiB

supertrees

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

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i = 0; i < n;i++){
		if(p[i][i] != 1) return 0;
		for(int j = i + 1;j < n;j++){
			if(p[i][j] != p[j][i] || p[i][j] == 3) return 0;
		}
	}

	vector<bool> vis(n, false);

	for(int i = 0; i < n;i++){
		if(vis[i]) continue;
		vis[i] = true;
		vector<int> curr(1, i);
		for(int j = 0; j < n;j++){
			if(p[i][j] != 0 && vis[j]) return 0;
			if(p[i][j] != 0) curr.push_back(j), vis[j] = true;
		}
		int m = curr.size();
		vector<vector<int>> branches;
		vector<bool> temp(n, false);
		for(int a = 0; a < m;a++){
			if(temp[a]) continue;
			vector<int> add;
			add.push_back(a);
			for(int b = a+1; b < m;b++){
				if(p[a][b] == 1){
					add.push_back(b);
					temp[b] = true;
				}

			}
		}
		
		for(vector<int> x : branches){
			for(int a : x){
				for(int b : x){
					if(a == b) continue;
					if(p[a][b] != 1) return 0;
					ans[a][b] = 1;
				}
			}
		}

		for(int x = 0; x < branches.size();x++){
			vector<bool> bb(n);
			for(int a : branches[x]){
				bb[a] = true;
			}
			for(int a : branches[x]){
				for(int b : curr){
					if(bb[b]) continue;
					if(p[a][b] != 2) return 0;
				}
			}
		}

		for(int j = 1; j < curr.size();j++){
			for(int k = 0; k < n;k++){
				int a = curr[j];
				int b = curr[0];
				if(a == k || b == k) continue;
				bool ok1 = p[a][k] >=1;
				bool ok2 = p[b][k] >=1;
				if(ok1 != ok2) return 0;
			}
		}

		for(int x = 0; x < branches.size() - 1; x++){
			ans[branches[x][0]][branches[x+1][0]] = ans[branches[x+1][0]][branches[x][0]] = 1;
		} ans[branches[0][0]][branches[branches.size()-1][0]] = ans[branches[branches.size()-1][0]][branches[0][0]] = 1;
	}

	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int x = 0; x < branches.size();x++){
      |                  ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int j = 1; j < curr.size();j++){
      |                  ~~^~~~~~~~~~~~~
supertrees.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int x = 0; x < branches.size() - 1; x++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

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