Submission #576180

#	Time	Username	Problem	Language	Result	Execution time	Memory
576180		Vanilla	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	204 ms	31044 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1002;
vector <int> ad1[maxn];
vector <int> ad2[maxn];
int d[maxn];
vector <int> comp;
bitset <maxn> vis;
bitset <maxn> vis1;
int b[maxn][maxn];

int get_dad (int x) {
	return d[x] = (x == d[x] ? x: get_dad(d[x]));
}

void merge (int a, int b){
	a = get_dad(a);
	b = get_dad(b);
	d[b] = a;
}

void dfs (int u) {
	vis[u] = 1;
	comp.push_back(u);
	for (int v: ad2[u]) {
		if (!vis[v]) {
			// merge(u, v);
			dfs(v);
		}
	}
}

void dfs1 (int u) {
	vis1[u] = 1;
	for (int v: ad1[u]) {
		if (!vis1[v]) {
			b[get_dad(u)][v] = b[v][get_dad(u)] = 1;
			merge(v, u);
			dfs1(v);
		}
	}
}


int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; i++){
		d[i] = i;
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < i; j++){
			if (p[i][j] == 2){
				ad2[i].push_back(j);
				ad2[j].push_back(i);
			}
			else if (p[i][j] == 1) {
				ad1[i].push_back(j);
				ad1[j].push_back(i);
			}
			
		}
	}
	for (int i = 0; i < n; i++){
		if (!vis[i]) {
			comp.clear();
			dfs(i);
			if (comp.size() > 1)
				for (int k = 0; k < comp.size(); k++){
					b[comp[k]][comp[(k + 1) % comp.size()]] = b[comp[(k + 1) % comp.size()]][comp[k]] = 1;
				}
		}
	}
	for (int i = 0; i < n; i++){
		if (!vis1[i]) {
			dfs1(i);
		}
	}
	vector <vector <int> > s (n, vector <int> (n));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			s[i][j] = b[i][j];
			// if (b[i][j] && j > i) {
			// 	cout << i << " " << j << "\n";
			// }
		}
	}
	build(s);
	return 1;
}

Compilation message (stderr)

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

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