Submission #744735

#	Time	Username	Problem	Language	Result	Execution time	Memory
744735		josanneo22	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	185 ms	26180 KiB

supertrees

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 

#include "supertrees.h"
#include <vector>
void build(vector<vector<int>> b);
const int N = 1005;
int n, mx, vis[N];
vector<int> block, edge, circle;
vector<vector<int>> path, ans;
void st(int u, int v) {
	ans[u][v] = 1; ans[v][u] = 1;
}
void dfs(int u) {
	vis[u] = 1;
	block.push_back(u);
	for (int v = 0; v < n; v++) {
		mx = max(mx, path[u][v]);
		if (!vis[v] && path[u][v]) dfs(v);
	}
}
void find_branches(int u) {
	vis[u] = 2;
	edge.push_back(u);
	for (int v = 0; v < n; v++) {
		if (vis[v] == 1 && path[u][v] == 1) find_branches(v);
	}
}
/*
	solution explaination:
		observation 1: we can nveer construct if some path[i][j] is 3
		observation 2: if path[i][j] is 0: nothing happens
					   if path[i][j] is 1: meaning that is connected once
					   if path[i][j] is 2: meaning that there must be a cycle
		observation 3: the graph is only a cycle with branches going out of it
					   if consists of two cycles, we might get graph[i][j]>=4
					   and inside the cycle, all graph[i][j] must be 1
*/
int construct(std::vector<std::vector<int>> p) {
	path = p; n = p.size(); ans.resize(n);
	for (int i = 0; i < n; i++) ans[i].resize(n);
	//run each connected blocks check if there is a need to add cycle
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;//if visisted
		mx = 1; block.clear(); dfs(i);
		//record maximum such that there is no path[i][j]>=3
		//clear block and dfs
		if (mx == 3) return 0;
		//now my blocks should have all connected
		int sz = block.size();
		for (int f = 1; f < sz; f++) {
			for (int k = 0; k < f; k++) {
				if (!path[block[f]][block[k]]) return 0;//all path[i][j] be at least>=1
			}
		}
		//if max is just 1, just make a star
		if (mx == 1) {
			for(int j=1;j<sz;j++)st(block[0], block[j]);
		}
		else {
			circle.clear();
			for (int j = 0; j < sz; j++) {
				int k = block[j];//current index
				if (vis[k] != 1) continue;
				edge.clear();
				find_branches(k);//find all branches from current index
				for (int a = 1; a < edge.size(); a++) {
					for (int b = 0; b < a; b++) {
						if (path[edge[a]][edge[b]] != 1) return 0;
					}
					st(edge[0], edge[a]);//make star from edge[0] to all branches
				}
				circle.push_back(edge[0]);//edge[0] is inside circle now
			}
			//note that cycle size must be >=3
			if (circle.size() <= 2) return 0;
			for (int j = 0; j < circle.size(); j++) st(circle[j], circle[(j + 1) % circle.size()]);
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int a = 1; a < edge.size(); a++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int j = 0; j < circle.size(); j++) st(circle[j], circle[(j + 1) % circle.size()]);
      |                    ~~^~~~~~~~~~~~~~~

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