Submission #559763

#	Time	Username	Problem	Language	Result	Execution time	Memory
559763		AlperenT	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	268 ms	22408 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);

		// cout << a << " " << b << "+\n";
 
		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();

	for(auto i : graph){
		for(auto j : i){
			if(j == 3) return 0;
		}
	}
 
	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);

			vector<int> nodevec;
 
			for(auto u : curnodes){
				if(graph[v][u] == 3){
					bool flag = true;
 
					for(auto w : nodevec){
						if(graph[u][w] != 3) flag = false;
					}
 
					if(flag) nodevec.push_back(u);
				}
			}

			if(nodevec.size() >= 3){
				for(auto u : nodevec) dsu.setunion(v, u);
				dsu.type[dsu.setfind(v)] = 3;
				for(auto u : nodevec) curnodes.erase(u);

				vector<int> tmp;
				for(auto x : dsu.nodes[dsu.setfind(v)]) tmp.push_back(x);
	 
				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;

				nodevec.push_back(v);

				for(auto ww : nodevec){
					vector<int> ones;

					for(int u = 0; u < n; u++){
						if(dsu.setfind(ww) != dsu.setfind(u) && dsu.type[dsu.setfind(u)] == 0){
							if(graph[ww][u] == 1){
								int typeu = dsu.type[dsu.setfind(ww)];
			 
								bool flag = true;
			 
								for(auto x : dsu.nodes[dsu.setfind(ww)]){
									for(auto y : dsu.nodes[dsu.setfind(u)]){
										if(x == ww && graph[x][y] != 1) flag = false;
										else if(x != ww && graph[x][y] != typeu) flag = false; 
									}
								}

								// cout << u << " " << flag << "\n";
			 
								if(flag){
									ones.push_back(u);
									ans[ww][u] = ans[u][ww] = 1;
								}
								else return 0;
							}
						}
					}

					for(auto u : ones){
						// cout << ww << " " << u << "*\n";
						dsu.setunion(ww, u);
					}
				}
			}
			// else curnodes.insert(v);
		}
		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);

			vector<int> nodevec;
 
			for(auto u : curnodes){
				if(graph[v][u] == 2){
					bool flag = true;
 
					for(auto w : nodevec){
						if(graph[u][w] != 2) flag = false;
					}
 
					if(flag) nodevec.push_back(u);
				}
			}

			if(nodevec.size() >= 2){
				for(auto u : nodevec) dsu.setunion(v, u);
				dsu.type[dsu.setfind(v)] = 2;
				for(auto u : nodevec) curnodes.erase(u);

				vector<int> tmp;
				for(auto x : dsu.nodes[dsu.setfind(v)]) tmp.push_back(x);
	 
				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;

				// cout << v << ": ";

				// for(auto u : nodevec) cout << u << " ";

				// cout << "\n";

				nodevec.push_back(v);

				for(auto ww : nodevec){
					vector<int> ones;

					for(int u = 0; u < n; u++){
						if(dsu.setfind(ww) != dsu.setfind(u) && dsu.type[dsu.setfind(u)] == 0){
							if(graph[ww][u] == 1){
								int typeu = dsu.type[dsu.setfind(ww)];
			 
								bool flag = true;
			 
								for(auto x : dsu.nodes[dsu.setfind(ww)]){
									for(auto y : dsu.nodes[dsu.setfind(u)]){
										if(x == ww && graph[x][y] != 1) flag = false;
										else if(x != ww && graph[x][y] != typeu) flag = false; 
									}
								}

								// cout << u << " " << flag << "\n";
			 
								if(flag){
									ones.push_back(u);
									ans[ww][u] = ans[u][ww] = 1;
								}
								else return 0;
							}
						}
					}

					for(auto u : ones){
						// cout << ww << " " << u << "*\n";
						dsu.setunion(ww, u);
					}
				}
			}
			// else curnodes.insert(v);
		}
		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;

			vector<int> nodevec;
 
			for(auto u : curnodes){
				if(graph[v][u] == 1){
					bool flag = true;
 
					for(auto w : nodevec){
						if(graph[u][w] != 1) flag = false;
					}
 
					if(flag) nodevec.push_back(u);
				}
			}

			if(nodevec.size() >= 1){
				for(auto u : nodevec) dsu.setunion(v, u);
				dsu.type[dsu.setfind(v)] = 1;
				for(auto u : nodevec) curnodes.erase(u);

				vector<int> tmp;
				for(auto x : dsu.nodes[dsu.setfind(v)]) tmp.push_back(x);
	 
				for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
			}
			// else curnodes.insert(v);
		}
		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
 
	// 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;
}

// int main(){
// 	construct({{1, 2, 1, 2, 2, 2, 1}, {2, 1, 2, 1, 2, 2, 2}, {1, 2, 1, 2, 2, 2, 1}, {2, 1, 2, 1, 2, 2, 2}, {2, 2, 2, 2, 1, 1, 2}, {2, 2, 2, 2, 1, 1, 2}, {1, 2, 1, 2, 2, 2, 1}});
// }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
      |                    ~~~~~~^~~~~~~~~~~~
supertrees.cpp:160:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i = 0; i + 1 < tmp.size(); i++) ans[tmp[i]][tmp[i + 1]] = ans[tmp[i + 1]][tmp[i]] = 1;
      |                    ~~~~~~^~~~~~~~~~~~
supertrees.cpp:243:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |     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: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4