제출 #331170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331170		dennisstar	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	266 ms	23404 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) 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=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=2*n; i<3*n; i++) for (auto &j:v[i]) for (auto &k:v[i]) if (j!=k&&p[j][k]!=3) 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), c(n);
	for (int i=0; i<n; i++) for (auto &j:p[i]) if (j) c[i]|=(1<<j-1);
	for (auto &i:c) if (i==7) return 0;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int j=1; j<v[i].size(); j++)
      |                 ~^~~~~~~~~~~~
supertrees.cpp:49:63: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |  for (int i=0; i<n; i++) for (auto &j:p[i]) if (j) c[i]|=(1<<j-1);
      |                                                              ~^~
supertrees.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   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:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    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:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    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: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4