Submission #827236

#	Time	Username	Problem	Language	Result	Execution time	Memory
827236		tomruk	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	199 ms	28024 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n,(vector<int>(n,0)));
	vector<vector<int>> myp(n,vector<int>(n,0));
	vector<bool> used(n,0);
	vector<int> col(n,0);
	set<int> cur;
	function<void(int)> dfs = [&](int v)->void{
		used[v] = 1;
		cur.insert(v);
		for(int i = 0;i<n;i++){
			if(!used[i] && p[v][i] == 1){
				col[i] = col[v];
				dfs(i);
				answer[v][i] = 1;
				answer[i][v] = 1;
			}
		}
	};
	for(int i = 0;i<n;i++){
		if(used[i])continue;
		int now = i;
		vector<int> tmp;
		int num = -1;
		set<int> s;
		for(int j = 0;j<n;j++){
			if(p[now][j] >= 2){
				if(num == -1)
					num = p[now][j];
				if(num != p[now][j])
					return 0;
				s.insert(j);
			}
		}
		while(s.size()){
			tmp.push_back(now);
			vector<int> del;
			for(auto u:s){
				if(p[now][u] != num){
					del.push_back(u);
				}
			}
			for(auto u:del)
				s.erase(u);
			if(s.empty())
				break;
			now = *s.begin();
		}
		if(tmp.empty())
			continue;
		if(tmp.size() < 3){
			return 0;
		}
		for(int j = 0;j<tmp.size();j++){
			answer[tmp[j]][tmp[(j + 1)%tmp.size()]] = 1;
			answer[tmp[(j + 1)%tmp.size()]][tmp[j]] = 1;
		}
		if(num == 3){
			if(tmp.size() < 4)
				return 0;
			answer[tmp[0]][tmp[2]] = 1;
			answer[tmp[2]][tmp[0]] = 1;
		}
		cur.clear();
		for(auto u:tmp){
			col[u] = u;
			dfs(u);
		}
		for(auto u:cur){
			for(int j = 0;j<n;j++){
				if(p[u][j] == 0 && cur.count(j))
					return 0;
				if(p[u][j] == 1 && (!cur.count(j) || col[j] != col[u]))
					return 0;
				if(p[u][j] > 1 && (p[u][j] != num || !cur.count(j)))
					return 0;
				if(p[u][j] > 1 && col[u] == col[j])
					return 0;
			}
		}
		for(auto u:cur){
			for(auto c:cur){
				myp[u][c] = num;
				if(col[u] == col[c])
					myp[u][c] = 1;
			}
		}
	}
	for(int i = 0;i<n;i++){
		if(!used[i]){
			cur.clear();
			col[i] = i;
			dfs(i);
			for(auto u:cur){
				for(int j = 0;j<n;j++){
					if(p[u][j] == 0 && cur.count(j))
						return 0;
					if(p[u][j] == 1 && (!cur.count(j) || col[j] != col[u]))
						return 0;
					if(p[u][j] > 1)
						return 0;
				}
			}
			for(auto u:cur){
				for(auto c:cur){
					myp[u][c] = 1;
				}
			}
		}
	}
	if(myp != p)
		return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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