Submission #823018

#	Time	Username	Problem	Language	Result	Execution time	Memory
823018		NothingXD	Connecting Supertrees (IOI20_supertrees)	C++17	65 / 100	173 ms	30028 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin() x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e3 + 10;

int n, p[maxn][maxn], dsu[maxn], comp[maxn];
int ans[maxn][maxn];
vector<int> ver[maxn];
int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

void merge(int u, int v){
	if ((u = getdsu(u)) == (v = getdsu(v))) return;
	ans[u][v] = ans[v][u] = 1;
	dsu[u] = v;
}

bool merge2(int u, int v){
//	debug(u, v);
	u = comp[u], v = comp[v];
	if (u == v) return true;
	for (auto x: ver[u]){
		for (auto y: ver[v]){
			if (p[x][y] != 2) return false;
		}
	}
	for (auto x: ver[v]){
		if (x == v) continue;
		ver[u].push_back(x);
		comp[x] = u;
	}
	ver[u].push_back(v);
	comp[v] = u;
	return true;
}

int construct(vector<vector<int>> P) {
	n = P.size();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			p[i][j] = P[i][j];
		}
	}
	memset(dsu, -1, sizeof dsu);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] != p[j][i]) return 0;
			if (p[i][j] == 1) merge(i, j);
		}
	}
//	debug(1);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] == 2 && getdsu(i) == getdsu(j)) return 0;
		}
	}
//	debug(2);
	for (int i = 0; i < n; i++){
		int x = getdsu(i);
//		debug(i, x);
		ver[x].push_back(i);
		comp[i] = x;
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (p[i][j] == 2){
				if (!merge2(i, j)) return 0;
			}
		}
	}
//	debug(3);
	for (int i = 0; i < n; i++){
		ver[i].clear();
	}
	for (int i = 0; i < n; i++){
		if (dsu[i] == -1){
//			debug(i, comp[i]);
			ver[comp[i]].push_back(i);
		}
	}
	for (int i = 0; i < n; i++){
//		debug(i, ver[i].size());
		if (ver[i].size() < 2) continue;
		if (ver[i].size() == 2) return 0;
		for (int j = 1; j < ver[i].size(); j++){
			ans[ver[i][j-1]][ver[i][j]] = ans[ver[i][j]][ver[i][j-1]] = 1;
		}
		ans[ver[i][0]][ver[i].back()] = ans[ver[i].back()][ver[i][0]] = 1;
	}
//	debug(4);
	vector<vector<int>> res(n);
	for (int i = 0; i < n; i++){
		res[i].resize(n);
		for (int j = 0; j < n; j++){
			res[i][j] = ans[i][j];
		}
	}
	build(res);
	return 1;
}

Compilation message (stderr)

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

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