Submission #559714

#	Time	Username	Problem	Language	Result	Execution time	Memory
559714		AlperenT	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	216 ms	22532 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1000 + 5;
 
struct DSU{
	int par[N], type[N];
	set<int> nodes[N];
 
	void reset(int n){
		for(int i = 0; i < n; i++) par[i] = i, type[i] = 0, nodes[i].insert(i);
	}
 
	int setfind(int a){
		if(par[a] == a) return a;
		else return par[a] = setfind(par[a]);
	}
 
	void setunion(int a, int b){
		a = setfind(a), b = setfind(b);
 
		if(a != b){
			if(nodes[b].size() > nodes[a].size()) swap(a, b);
			par[b] = par[a];
			type[b] = -1;
			for(auto x : nodes[b]) nodes[a].insert(x);
			nodes[b].clear();
		}
	}
};
 
DSU dsu;
 
int construct(vector<vector<int>> graph) {
	int n = graph.size();
 
	vector ans(n, vector(n, 0));
 
	dsu.reset(n);
 
	// finding 3 cycles
 
	set<int> curnodes;
 
	for(int i = 0; i < n; i++) curnodes.insert(i);
 
	for(int v = 0; v < n; v++){
		if(curnodes.count(v) && dsu.type[dsu.setfind(v)] == 0){
			curnodes.erase(v);
 
			for(auto u : curnodes){
				if(graph[v][u] == 3){
					bool flag = true;
 
					for(auto w : dsu.nodes[dsu.setfind(v)]){
						if(graph[u][w] != 3) flag = false;
					}
 
					if(flag){
						dsu.type[dsu.setfind(v)] = dsu.type[dsu.setfind(u)] = 3;
						dsu.setunion(v, u);
					}
				}
			}
 
			for(auto u : dsu.nodes[dsu.setfind(v)]) curnodes.erase(u);
		}
		else curnodes.erase(v);
	}
 
	// finding 2 cycles
 
	curnodes.clear();
 
	for(int i = 0; i < n; i++) curnodes.insert(i);
 
	for(int v = 0; v < n; v++){
		if(curnodes.count(v) && dsu.type[dsu.setfind(v)] == 0){
			curnodes.erase(v);
 
			for(auto u : curnodes){
				if(graph[v][u] == 2){
					bool flag = true;
 
					for(auto w : dsu.nodes[dsu.setfind(v)]){
						if(graph[u][w] != 2) flag = false;
					}
 
					if(flag){
						dsu.type[dsu.setfind(v)] = dsu.type[dsu.setfind(u)] = 2;
						dsu.setunion(v, u);
					}
				}
			}
 
			for(auto u : dsu.nodes[dsu.setfind(v)]) curnodes.erase(u);
		}
		else curnodes.erase(v);
	}
 
	// finding 1 cycles
 
	curnodes.clear();
 
	for(int i = 0; i < n; i++) curnodes.insert(i);
 
	for(int v = 0; v < n; v++){
		if(curnodes.count(v) && dsu.type[dsu.setfind(v)] == 0){
			curnodes.erase(v);
			dsu.type[dsu.setfind(v)] = 1;
 
			for(auto u : curnodes){
				if(graph[v][u] == 1){
					bool flag = true;
 
					for(auto w : dsu.nodes[dsu.setfind(v)]){
						if(graph[u][w] != 1) flag = false;
					}
 
					if(flag){
						dsu.type[dsu.setfind(v)] = dsu.type[dsu.setfind(u)] = 1;
						dsu.setunion(v, u);
					}
				}
			}
 
			for(auto u : dsu.nodes[dsu.setfind(v)]) curnodes.erase(u);
		}
		else curnodes.erase(v);
	}
 
	// for(int i = 0; i < n; i++){
	// 	cout << i << " " << dsu.type[i] << ": ";
	// 	for(auto v : dsu.nodes[i]) cout << v << " ";
	// 	cout << "\n";
	// }
 
	// creating edges
 
	for(int i = 0; i < n; i++){
		if(dsu.type[i] == 1){
			vector<int> tmp;
			for(auto v : dsu.nodes[i]) tmp.push_back(v);
 
			for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
		}
		else if(dsu.type[i] == 2){
			if(dsu.nodes[i].size() <= 2) return 0;
 
			vector<int> tmp;
			for(auto v : dsu.nodes[i]) tmp.push_back(v);
 
			for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
			ans[tmp.back()][tmp.front()] = ans[tmp.front()][tmp.back()] = 1;
		}
		if(dsu.type[i] == 3){
			if(dsu.nodes[i].size() <= 3) return 0;
 
			vector<int> tmp;
			for(auto v : dsu.nodes[i]) tmp.push_back(v);
 
			for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
			ans[tmp.back()][tmp.front()] = ans[tmp.front()][tmp.back()] = 1;
			ans[0][2] = ans[2][0] = 1;
		}
	}
 
	// connecting 1 cycles to other cycles
 
	for(int v = 0; v < n; v++){
		int cnt = 0;
 
		for(int u = 0; u < n; u++){
			if(dsu.type[dsu.setfind(v)] == 1 && dsu.setfind(v) != dsu.setfind(u)){
				if(graph[v][u] == 1){
					int typeu = dsu.type[dsu.setfind(u)];
 
					bool flag = true;
 
					for(auto x : dsu.nodes[dsu.setfind(v)]){
						for(auto y : dsu.nodes[dsu.setfind(u)]){
							if(y == u && graph[x][y] != 1) flag = false;
							else if(y != u && graph[x][y] != typeu) flag = false; 
						}
					}
 
					if(flag){
						dsu.setunion(v, u);
						ans[v][u] = ans[u][v] = 1;
					}
					else return 0;
 
					cnt++;
				}
			}
		}
 
		if(cnt >= 2) return 0;
	}
 
	for(int v = 0; v < n; v++){
		for(int u = 0; u < n; u++){
			if(dsu.setfind(v) != dsu.setfind(u) && graph[v][u] != 0) return 0;
		}
	}
 
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:147:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
      |                   ~~~~~~^~~~~~~~~~~~
supertrees.cpp:155:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |    for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
      |                   ~~~~~~^~~~~~~~~~~~
supertrees.cpp:164:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
      |                   ~~~~~~^~~~~~~~~~~~

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