Submission #652029

#	Time	Username	Problem	Language	Result	Execution time	Memory
652029		mychecksedad	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	199 ms	22204 KiB

supertrees

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

struct Dsu{
	vector<int> s, p;
	Dsu(int n){
		s.resize(n + 1, 1);
		p.resize(n + 1);
		for(int i = 0; i <= n; ++i) p[i] = i;
	}
	int find(int v){
		if(p[v] == v) return v;
		return (p[v] = find(p[v]));
	}
	void merge(int a, int b){
		a = find(a);
		b = find(b);
		if(a != b){
			if(s[a] > s[b]) swap(a, b);
			p[a] = b;
			s[b] += s[a];
		}
	}
};
void build(vector<vector<int>> _b);

int construct(vector<vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	Dsu d(n);
	vector<vector<int>> comp;

	bool ok = 1;

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(p[i][j] == 3){
				return 0;
			}
			if(p[i][j] != 0){
				d.merge(i, j);
			}
		}
	}
	vector<int> s (n, -1);
	for(int i = 0; i < n; ++i){
		int c = d.find(i);
		if(s[c] == -1){
			s[c] = comp.size();
			comp.pb({i});
		}else{
			comp[s[c]].pb(i);
		}
	}
	vector<bool> used(n);
	for(auto v: comp){
		vector<int> in, notin;
		for(int x: v){
			bool inner = 1;
			for(int y: v){
				if(p[x][y] == 0){
					return 0;
				}
				if(p[x][y] != 2 && x != y) inner = 0;
			}
			if(inner){
				in.pb(x);
				used[x] = 1;
			}else{
				notin.pb(x);
			}
		}
		for(int u: notin){
			if(used[u]){
				continue;
			}
			used[u] = 1;
			in.pb(u);
			vector<int> q;
			q.pb(u);
			for(int x: notin){
				if(p[u][x] == 1 && u != x){
					if(used[x]){
						return 0;
					}
					q.pb(x);
					used[x] = 1;
				}
			}
			for(int a: q){
				for(int b: q){
					if(p[a][b] != 1){
						return 0;
					}
				}
			}
			for(int j = 0; j < q.size() - 1; ++j){
				answer[q[j]][q[j + 1]] = 1;
				answer[q[j + 1]][q[j]] = 1;
			}
		}
		if(in.size() == 2){
			return 0;
		}
		if(in.size() > 1){
			for(int j = 0; j < in.size(); ++j){
				answer[in[j]][in[(j + 1) % (in.size())]] = 1;
				answer[in[(j + 1) % (in.size())]][in[j]] = 1;
			}
		}
	}




	build(answer);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for(int j = 0; j < q.size() - 1; ++j){
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for(int j = 0; j < in.size(); ++j){
      |                   ~~^~~~~~~~~~~
supertrees.cpp:40:7: warning: unused variable 'ok' [-Wunused-variable]
   40 |  bool ok = 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