Submission #302236

#	Time	Username	Problem	Language	Result	Execution time	Memory
302236		leejseo	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	276 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 = true, ST5 = false;

int construct(vector<vector<int>> p) {
	int N = p.size();
	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){
		int x = true; // pass
	}
	if (!ST5){
		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){
					int x = C[0], y = C[1];
					ans[x][y] = ans[y][x] = 1;
					continue;
				}
				int x1 = C[0], y1 = C[1];
				if (p[x1][y1] == 2){
					for (int j=0; j<M; j++){
						int x = C[j];
						int y = C[(j+1) % M];
						ans[x][y] = ans[y][x] = 1;
					}
				}
				else{
					for (int j=0; j<M-1; j++){
						int x = C[j];
						int y = C[j+1];
						ans[x][y] = ans[y][x] = 1;
					}
				}
			}
		}
		build(ans);
		return 1;
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:18: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
  104 |      if (p[i][j] > 0 != disj.chk(i, j)){
supertrees.cpp:130:7: warning: unused variable 'x' [-Wunused-variable]
  130 |   int x = true; // pass
      |       ^
supertrees.cpp:142:17: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
  142 |     if (p[i][j] > 0 != disj.chk(i, j)){

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