Submission #600125

#	Time	Username	Problem	Language	Result	Execution time	Memory
600125		definitelynotmee	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	179 ms	24064 KiB

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);
		group = matrix<int>(n);
		for(int i = 0; i < n; i++)
			group[i].push_back(i);
	}
	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){
		// cout << "->";
		// for(int i : g)
		// 	cout << i << ' ';
		// cout << '\n';
		int line = 1;
		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 (stderr)

supertrees.cpp: In lambda function:
supertrees.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int i = 1; i < g.size(); i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:100:12: warning: unused variable 'j' [-Wunused-variable]
  100 |    for(int j : g){
      |            ^
supertrees.cpp:99:11: warning: unused variable 'i' [-Wunused-variable]
   99 |   for(int i : g){
      |           ^

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