Submission #826990

#	Time	Username	Problem	Language	Result	Execution time	Memory
826990		tomruk	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	176 ms	22836 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<bool> used(n,0);
	function<void(int)> dfs = [&](int v)->void{
		used[v] = 1;
		for(int i = 0;i<n;i++){
			// cout << v << ' ' << i << endl;
			// cout << p[v][i] << endl;
			if(!used[i] && p[v][i]){
				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){
				s.insert(j);
			}
		}
		// cout << "HEy" << endl;
		while(s.size()){
			// cout << now << ' ' << i << endl;
			tmp.push_back(now);
			used[now] = 1;
			vector<int> del;
			for(auto u:s){
				if(p[now][u] < 2){
					del.push_back(u);
				}
			}
			for(auto u:del)
				s.erase(u);
			if(s.empty())
				break;
			now = *s.begin();
		}
		// cout << tmp.size() << endl;
		if(tmp.empty())
			continue;
		if(tmp.size() < 3){
			return 0;
		}
		for(int i = 0;i<tmp.size();i++){
			answer[tmp[i]][tmp[(i + 1)%tmp.size()]] = 1;
			answer[tmp[(i + 1)%tmp.size()]][tmp[i]] = 1;
		}
		if(p[tmp[0]][tmp[1]] == 3){
			if(tmp.size() < 4)
				return 0;
			answer[tmp[i]][tmp[(i + 2)%tmp.size()]] = 1;
			answer[tmp[(i + 2)%tmp.size()]][tmp[i]] = 1;
		}
		for(auto u:tmp){
			dfs(u);
		}
	}
	for(int i = 0;i<n;i++){
		// cout << used[i] << endl;
		if(!used[i])
			dfs(i);
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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