제출 #302912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302912		leejseo	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	298 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> ans;

struct DisjointSet{
	int par[1005];
	DisjointSet(){
		for (int i=0; i<1005; i++) par[i] = i;
	}
	int root(int u){
		if (par[u] == u) return u;
		return par[u] = root(par[u]); 
	}
	bool chk(int u, int v){
		return root(u) == root(v);
	}
	void merge(int u, int v){
		u = root(u); v = root(v);
		if (u != v) par[u] = v;
	}
} disj, uf;

const bool ST4 = false, ST5 = false;

bool chk[1005];

int construct(vector<vector<int>> p) {
	int N = p.size();
	for (int i=0; i<N; i++)
		for (int j=0; j<N; j++)
			if (p[i][j] == 3) return 0;
	for (int i = 0; i < N; i++) {
		vector<int> row;
		for (int j=0; j<N; j++) row.push_back(0);
		ans.push_back(row);
	}
	{
		bool subtask1 = true;
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] != 1){
					subtask1 = false;
				}
			}
			if (!subtask1) break;
		}
		if (subtask1){
			for (int i=0; i<N-1; i++){
				ans[i][i+1] = 1;
				ans[i+1][i] = 1;
			}
			build(ans);
			return 1;
		}
	}
	{
		bool subtask2 = true;
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] > 1){
					subtask2 = false;
					break;
				}
			}
		}
		if (subtask2){
			for (int i=0; i<N; i++){
				for (int j=0; j<N; j++){
					if (p[i][j] && !disj.chk(i, j)){
						disj.merge(i, j);
						ans[i][j] = ans[j][i] = 1;
					}
				}
			}
			for (int i=0; i<N; i++){
				for (int j=0; j<N; j++){
					if ((bool) p[i][j] != disj.chk(i, j)){
						return 0;
					}
				}
			}
			build(ans);
			return 1;
		}
	}
	{
		bool subtask3 = true;
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (i != j && p[i][j] % 2 == 1){
					subtask3 = false;
					break;
				}
			}
			if (subtask3 == false) break;
		}
		if (subtask3){
			for (int i=0; i<N; i++){
				for (int j=0; j<N; j++){
					if (p[i][j] > 0 && !disj.chk(i, j)){
						disj.merge(i, j);
					}
				}
			}
			for (int i=0; i<N; i++){
				for (int j=0; j<N; j++){
					if (p[i][j] > 0 != disj.chk(i, j)){
						return 0;
					}
				}
			}
			for (int i=0; i<N; i++){
				if (disj.root(i) == i){
					vector<int> C;
					for (int j=0; j<N; j++){
						if (disj.chk(i, j)) C.push_back(j);
					}
					int M = C.size();
					if (M == 1) continue;
					if (M == 2) return 0;
					for (int j=0; j<M; j++){
						int x = C[j];
						int y = C[(j+1) % M];
						ans[x][y] = ans[y][x] = 1;
					}
				}
			}
			build(ans);
			return 1;
		}
	}
	if (!ST4){
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] == 1 && !uf.chk(i, j)) uf.merge(i, j);
			}
		}
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] == 2 && !disj.chk(uf.root(i), uf.root(j))){
					disj.merge(uf.root(i), uf.root(j));
				}
			}
		}
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] == 0){
					if (uf.chk(i, j) || disj.chk(uf.root(i), uf.root(j))) return 0;
				}
				if (p[i][j] == 1){
					if (uf.root(i) != uf.root(j)) return 0;
					//if (i != j && disj.chk(i, j)) return 0;
				}
				if (p[i][j] == 2){
					if (uf.chk(i, j)) return 0;
					if (!disj.chk(uf.root(i), uf.root(j))) return 0;
				}
			}
		}
		uf = DisjointSet();
		disj = DisjointSet();
	}
	if (!ST5){
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] == 1 && !uf.chk(i, j)){
					uf.merge(i, j);
				}
			}
		}
		for (int i=0; i<N; i++){
			if (uf.root(i) == i){
				vector<int> I;
				for (int j=0; j<N; j++){
					if (uf.chk(i, j)) I.push_back(j);
				}
				int M = I.size();
				if (M == 1) continue;
				for (int j=0; j<M-1; j++){
					int x = I[j];
					int y = I[j+1];
					ans[x][y] = ans[y][x] = 1;
				}
			}
		}
		for (int i=0; i<N; i++){
			for (int j=0; j<N; j++){
				if (p[i][j] == 2 && !disj.chk(uf.root(i), uf.root(j))){
					disj.merge(uf.root(i), uf.root(j));
				}
			}
		}
		for (int i=0; i<N; i++){
			if (disj.root(i) == i){
				vector<int> C;
				for (int j=0; j<N; j++){
					if (disj.chk(i, j)) C.push_back(j);
				}
				int M = C.size();
				if (M == 2) return 0;
				if (M <= 2) continue;
				for (int j=0; j<M; j++){
					int x = C[j];
					int y = C[(j+1) % M];
					ans[x][y] = ans[y][x] = 1;
				}
			}
		}
		build(ans);
		return 1;
	}
	build(ans);
	return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:109:18: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
  109 |      if (p[i][j] > 0 != disj.chk(i, j)){

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