Submission #1051368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051368		pcc	슈퍼트리 잇기 (IOI20_supertrees)	C++17	21 / 100	142 ms	26196 KiB

supertrees

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

const int mxn = 1010;

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
		fill(sz,sz+mxn,1);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
	}
};

/*
std::vector<std::vector<int>> answer(n,vector<int>(n,0));
build(answer);
return 1;
*/

DSU chain,cyc;
int N;
vector<vector<int>> ans;
vector<vector<int>> tar;
vector<int> v[mxn];

void add_edge(int a,int b){
	assert(a != b);
	ans[a][b] = ans[b][a] = 1;
}

bool check(){
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			if(tar[i][j] == 0){
				if(chain.root(i) == chain.root(j))return false;
			}
			else if(tar[i][j] == 1){
				if(chain.root(i) != chain.root(j))return false;
			}
		}
	}
	return true;
}

int construct(std::vector<std::vector<int>> vvv) {
	tar = vvv;
	N = tar.size();
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			if(tar[i][j] == 1)chain.onion(i,j);
		}
	}
	ans = vector<vector<int>>(N,vector<int>(N,0));
	for(int i = 0;i<N;i++){
		v[chain.root(i)].push_back(i);
	}
	for(int i = 0;i<N;i++){
		for(int j = 1;j<v[i].size();j++){
			add_edge(v[i][j-1],v[i][j]);
		}
	}
	if(!check())return 0;
	build(ans);
	return 1;
}

Compilation message (stderr)

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

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