Submission #331164

#	Time	Username	Problem	Language	Result	Execution time	Memory
331164		dennisstar	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	272 ms	24320 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);
		if (p[i][j]==2) U[1].un(i, j);
		if (p[i][j]==3) U[2].un(i, j);
	}

	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),
		v[U[2].gp(i+1)-1+2*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=0; i<n; i++)
		U[3].un(U[0].gp(i+1)-1, U[1].gp(i+1)-1+n),
		U[3].un(U[0].gp(i+1)-1, U[2].gp(i+1)-1+2*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]++;
		if (v[i+2*n].size()>1) x[U[3].gp(i+2*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;
		}
		if (v[i+2*n].size()>1) {
			if (v[i+2*n].size()<4) return 0;
			for (int j=1; j<v[i+2*n].size(); j++) r[v[i+2*n][j-1]][v[i+2*n][j]]=r[v[i+2*n][j]][v[i+2*n][j-1]]=1;
			r[v[i+2*n][0]][v[i+2*n].back()]=r[v[i+2*n].back()][v[i+2*n][0]]=1;
			r[v[i+2*n][0]][v[i+2*n][2]]=r[v[i+2*n][2]][v[i+2*n][0]]=1;
		}
	}

	build(r);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int j=1; j<v[i].size(); j++)
      |                 ~^~~~~~~~~~~~
supertrees.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   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:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    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;
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int j=1; j<v[i+2*n].size(); j++) r[v[i+2*n][j-1]][v[i+2*n][j]]=r[v[i+2*n][j]][v[i+2*n][j-1]]=1;
      |                  ~^~~~~~~~~~~~~~~~

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