Submission #600118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600118	2022-07-20T13:18:33 Z	definitelynotmee	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>

struct UnionFind{
	vector<int> pai;
	matrix<int> group;

	int n;
	UnionFind(int sz = 0){
		n = sz;
		pai = vector<int>(n);
		iota(all(pai),0);
	}
	int find(int id){
		if(pai[id] == id)
			return id;
		return pai[id] = find(pai[id]);
	}
	void onion(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b)
			return;
		if(group[a].size() > group[b].size())
			swap(a,b);
		for(int i : group[a])
			group[b].push_back(i);
		group[a].clear();
		pai[a] = b;
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	matrix<int> resp(n,vector<int>(n));

	UnionFind connected(n);

	for (int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++){
			if(p[i][j])
				connected.onion(i,j);
		}
	}
	auto solveforgroup =[&](vector<int>& g){
		int line = 0;
		for(int i : g){
			for(int j : g){
				if(!p[i][j])
					return 0;
				line&=p[i][j];
			}
		}
		if(line){
			for(int i = 1; i < g.size(); i++){
				resp[g[i-1]][g[i]] = 1;
				resp[g[i]][g[i-1]] = 1;
			}
			return 1;
		}

		vector<int> count1(n);

		for(int i : g){
			for(int j : g){
				count1[i]+=p[i][j] == 1;
			}
		}

		vector<int> cycle, incycle(n);

		for(int i : g){
			if(count1[i] == 0)
				cycle.push_back(i);
			for(int j : g){
				if(p[i][j] == 1 && count1[i] > count1[j]){
					cycle.push_back(i);
					incycle[i] = 1;
					break;
				}
			}
		}
		for(int i : g){
			for(int j : g){
				if(incycle[i] && incycle[j] && p[i][j])
			}
		}


		return 1;
	}
	bool ok = 1;
	for(vector<int>& i : connected.group){
		if(i.size())
			ok&=solveforgroup(i);
	}
	if(!ok)
		return 0;
	build(resp);

	return 1;
}

Compilation message

supertrees.cpp:13:17: error: types may not be defined in alias template declarations
   13 | struct UnionFind{
      |                 ^
supertrees.cpp:15:2: error: 'matrix' does not name a type
   15 |  matrix<int> group;
      |  ^~~~~~
supertrees.cpp:11:15: error: two or more data types in declaration of 'type name'
   11 | using matrix= vector<vector<T>>
      |               ^~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:44:2: error: 'matrix' was not declared in this scope
   44 |  matrix<int> resp(n,vector<int>(n));
      |  ^~~~~~
supertrees.cpp:44:9: error: expected primary-expression before 'int'
   44 |  matrix<int> resp(n,vector<int>(n));
      |         ^~~
supertrees.cpp:46:23: error: class template argument deduction failed:
   46 |  UnionFind connected(n);
      |                       ^
supertrees.cpp:46:23: error: no matching function for call to 'UnionFind(int&)'
supertrees.cpp:18:2: note: candidate: 'template<class T> UnionFind(int)-> UnionFind<T>'
   18 |  UnionFind(int sz = 0){
      |  ^~~~~~~~~
supertrees.cpp:18:2: note:   template argument deduction/substitution failed:
supertrees.cpp:46:23: note:   couldn't deduce template parameter 'T'
   46 |  UnionFind connected(n);
      |                       ^
supertrees.cpp:13:8: note: candidate: 'template<class T> UnionFind(UnionFind<T>)-> UnionFind<T>'
   13 | struct UnionFind{
      |        ^~~~~~~~~
supertrees.cpp:13:8: note:   template argument deduction/substitution failed:
supertrees.cpp:46:23: note:   mismatched types 'UnionFind<T>' and 'int'
   46 |  UnionFind connected(n);
      |                       ^
supertrees.cpp: In lambda function:
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 = 1; i < g.size(); i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:65:5: error: 'resp' was not declared in this scope
   65 |     resp[g[i-1]][g[i]] = 1;
      |     ^~~~
supertrees.cpp:95:4: error: expected primary-expression before '}' token
   95 |    }
      |    ^
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:101:2: error: expected ',' or ';' before 'bool'
  101 |  bool ok = 1;
      |  ^~~~
supertrees.cpp:104:4: error: 'ok' was not declared in this scope
  104 |    ok&=solveforgroup(i);
      |    ^~
supertrees.cpp:106:6: error: 'ok' was not declared in this scope
  106 |  if(!ok)
      |      ^~
supertrees.cpp:108:8: error: 'resp' was not declared in this scope
  108 |  build(resp);
      |        ^~~~