Submission #303419

#	Time	Username	Problem	Language	Result	Execution time	Memory
303419		mechfrog88	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	266 ms	22264 KiB

supertrees

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

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n,vector<int>(n));
	vector<bool> visited(n,false);
	bool ok = true;
	for (int z=0;z<n && ok;z++){
		if (visited[z]) continue;
		vector <ll> g1;
		vector <ll> g2;
		vector <ll> g3;
		for (int x=0;x<n && ok;x++){
			if (z == x) continue;
			if (p[z][x] == 1){
				g1.push_back(x);
				visited[x] = true;
				for (int x1=0;x1<n && ok;x1++){
					if (p[z][x1] != p[x][x1]){
						ok = false;
					}
				}
			}
			else if (p[z][x] == 2){
				g2.push_back(x);
				visited[x] = true;
				for (int x1=0;x1<n && ok;x1++){
					if (x1 == x) continue;
					if (p[z][x1] == 0 && p[x][x1] != 0){
						ok = false;
					}
					if (p[z][x1] != 0 && p[x][x1] != 2){
						ok = false;
					}
				}
			}
			else if (p[z][x] == 3){
				g3.push_back(x);
				visited[x] = true;
				for (int x1=0;x1<n && ok;x1++){
					if (x1 == x) continue;	
					if (p[z][x1] == 0 && p[x][x1] != 0){
						ok = false;
					}
					if (p[z][x1] != 0 && p[x][x1] != 3){
						ok = false;
					}
				}
			}
		}
		for (int x=0;x<g1.size();x++){
			ans[z][g1[x]] = 1;
			ans[g1[x]][z] = 1;
		}
		if (g2.size() < 2 && g2.size() > 0) ok = false;
		else if (g2.size() > 0){
			for (int x=0;x<g2.size()-1;x++){
				ans[g2[x]][g2[x+1]] = 1;
			}
			ans[z][g2[0]] = 1;
			ans[z][g2[g2.size()-1]] = 1;
		}
		if (g3.size() < 3 && g3.size() > 0) ok = false;
		else if (g3.size() > 0){
			for (int x=0;x<g3.size()-1;x++){
				ans[g3[x]][g3[x+1]] = 1;
			}
			ans[z][g3[0]] = 1;
			ans[z][g3[g3.size()-1]] = 1;
			ans[g3[0]][g3[g3.size()-1]] = 1;
		}
	}
	if (ok){
		build(ans);
		return 1;
	} else {
		return 0;
	}
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int x=0;x<g1.size();x++){
      |                ~^~~~~~~~~~
supertrees.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int x=0;x<g2.size()-1;x++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for (int x=0;x<g3.size()-1;x++){
      |                 ~^~~~~~~~~~~~

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