Submission #600304

#	Time	Username	Problem	Language	Result	Execution time	Memory
600304		definitelynotmee	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	240 ms	24148 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);
			if(p[i][j] == 3)
				return 0;
		}
	}
	auto solveforgroup =[&](vector<int>& g){
		vector<int> incall(n);
		for(int i : g)
			incall[i] = 1;

		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;
		}
		if(g.size() <= 2){
			return 0;
		}
		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(!incycle[i] && count1[i] == 1)
				cycle.push_back(i), incycle[i] = 1;
			for(int j : g){
				if(p[i][j] == 1 && !incycle[j] && count1[i] < count1[j]){
					cycle.push_back(j);
					incycle[j] = 1;
					break;
				}
			}
		}
		UnionFind lines(n);

		for(int i : g){
			if(incycle[i])
				continue;
			for(int j : g){
				if(p[i][j] == 1 && !incycle[j]){
					lines.onion(i,j);
				}
			}
		}

		for(vector<int> & line : lines.group){
			if(line.empty() || !incall[line[0]] || incycle[line[0]]){
				continue;
			}
			for(int i : line){
				for(int j : line){
					if(p[i][j]!=1)
						return 0;
				}
			}
			for(int j = 1; j < line.size(); j++){
				resp[line[j-1]][line[j]] = 1;
				resp[line[j]][line[j-1]] = 1;
			}
			int root= -1, rootct =0;
			for(int k : cycle){
				int allright = 1, someright= 0;
				for(int i : line){
					allright&=p[k][i];
					someright|=p[k][i]==1;
				}
				if(allright!=someright)
					return 0;
				if(allright){
					root = k;
					rootct++;
				}
			}
			if(rootct > 1)
				return 0;
			if(rootct == 1){
				resp[line[0]][root] = 1;
				resp[root][line[0]] = 1;
			}
			if(rootct == 0){
				cycle.push_back(line[0]);
				incycle[line[0]] = 1;
			}
		}
		if(cycle.size() <= 1)
			return 0;

		for(int i : cycle){
			for(int j : cycle){
				if(i!=j && p[i][j]!=2)
					return 0;
			}
		}

		for(int i = 1; i < cycle.size(); i++){
			resp[cycle[i]][cycle[i-1]] = 1;
			resp[cycle[i-1]][cycle[i]] = 1;
		}

		resp[cycle[0]][cycle.back()] = 1;
		resp[cycle.back()][cycle[0]] = 1;
		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:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int i = 1; i < g.size(); i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for(int j = 1; j < line.size(); j++){
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp:163:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   for(int i = 1; i < cycle.size(); i++){
      |                  ~~^~~~~~~~~~~~~~

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