Submission #332006

#	Time	Username	Problem	Language	Result	Execution time	Memory
332006		dennisstar	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	285 ms	24428 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define eb emplace_back
using namespace std;

const int MX = 1e3 + 5;

struct DJS {
	int p[3*MX];
	int gp(int x) { return p[x]?(p[x]=gp(p[x])):x; }
	void un(int x, int y) {
		x++; y++;
		x=gp(x), y=gp(y);
		if (x!=y) p[y]=x;
	}
}U[4];

int construct(vector<vector<int>> p) {
	int n=p.size();
	vector<vector<int>> r;
	for (int i=0; i<n; i++) r.eb(vector<int>(n));

	for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (p[i][j]==1) U[0].un(i, j);
	for (int i=0; i<n; i++) if (U[0].gp(i+1)-1==i) {
		for (int j=0; j<n; j++) if (U[0].gp(j+1)-1==j) {
			if (p[i][j]==2) U[1].un(i, j);
			if (p[i][j]==3) return 0;
		}
	}

	vector<vector<int>> v(3*n);
	for (int i=0; i<n; i++)
		v[U[0].gp(i+1)-1].eb(i),
		v[U[1].gp(i+1)-1+n].eb(i);

	for (int i=0; i<n; i++)
		for (int j=1; j<v[i].size(); j++)
			for (int k=0; k<n; k++) if (k!=v[i][0]&&k!=v[i][j]&&p[v[i][0]][k]!=p[v[i][j]][k]) return 0;

	for (int i=n; i<2*n; i++) for (auto &j:v[i]) for (auto &k:v[i]) if (j!=k&&p[j][k]!=2) return 0;
	
	for (int i=0; i<n; i++)
		U[3].un(U[0].gp(i+1)-1, U[1].gp(i+1)-1+n);

	vector<int> x(n);
	for (int i=0; i<n; i++) if (v[i+n].size()>1) x[U[3].gp(i+n+1)-1]++;
	for (auto &i:x) if (i>=2) return 0;

	for (int i=0; i<n; i++) {
		for (int j=1; j<v[i].size(); j++) r[v[i][0]][v[i][j]]=r[v[i][j]][v[i][0]]=1;
		if (v[i+n].size()>1) {
			if (v[i+n].size()<3) return 0;
			for (int j=1; j<v[i+n].size(); j++) r[v[i+n][j-1]][v[i+n][j]]=r[v[i+n][j]][v[i+n][j-1]]=1;
			r[v[i+n][0]][v[i+n].back()]=r[v[i+n].back()][v[i+n][0]]=1;
		}
	}

	build(r);
	return 1;
}

Compilation message (stderr)

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

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