제출 #313701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313701		keta_tsimakuridze	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int par[N],sz[N],a[N][N],ans[N][N],type[N],k,i,n,u,v,x,y,fix[N],cycle[N];
vector<int> comp[N],V[N];
vector<vector<int> > answer;
int find_parent(int u){
	if(par[u]==u) return u;
	return par[u]=find_parent(par[u]);
}
void merge(int u,int v){
	u=find_parent(u);
	v=find_parent(v);
	if(u==v) return;
	if(sz[u]<sz[v]) swap(u,v);
	par[v]=u;
	sz[u]+=sz[v];
}
void Go(int u){
	for(k=0;k<comp[u].size();k++){
		for(i=k+1;i<comp[u].size();i++){
			int x=comp[u][k];
			int y=comp[u][i];
			if(a[x][y]==1 && ans[x][y]==0){
			 V[x].push_back(y),
			 V[y].push_back(x); }
		}
	}
	
	for(k=0;k<comp[u].size();k++){
		x=comp[u][k];
		if(fix[x]) continue;
		type[x]=1;
		if(!fix[x]){
			for(i=0;i<V[x].size();i++){
				fix[V[x][i]]=x; 
				 ans[x][V[x][i]]=ans[V[x][i]][x]=1;
			}
			for(i=0;i<comp[u].size();i++){
				y=comp[u][i];
				if(a[x][y]!=2) continue;
				if(type[y]==1){
					cycle[u]++;
				ans[x][y]=ans[y][x]=1;
				}
			}
		}
	}
}
bool check(){
	for(k=1;k<=n;k++){
		std::vector<int> row;
		row.resize(n);
		for(i=1;i<=n;i++){

			if(i==k) ans[k][i]=1;
			else {
				int x=find_parent(k);
				int y=find_parent(i);
				if(a[k][i]==0 && x==y)return 0;
				if(!type[k] && !type[i] && a[k][i]==2) return 0;
				if(type[k]&&cycle[k]==1) return 0;
			}
			row.push_back(ans[k][i]);
		}answer.push_back(row);
	}
	return 1;
}
int construct(std::vector<std::vector<int> > v){
	//[[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]]
	// type[i] =0 -- ciklshi araa 
	for(k=1;k<=n;k++)
	par[k]=k,sz[k]=1;
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			a[k][i]=v[k-1][i-1];
			if(a[k][i]==3) {
			return 0;	
			}
			if(a[k][i]!=0) merge(k,i);
		}
	}
	for(k=1;k<=n;k++){
		comp[find_parent(k)].push_back(k);
	} 
	for(int k=1;k<=n;k++){
		Go(k);
	}
	if(!check()) return 0;
	else{
		build(answer);
	}
	return 1;
}

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

supertrees.cpp: In function 'void Go(int)':
supertrees.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(k=0;k<comp[u].size();k++){
      |          ~^~~~~~~~~~~~~~~
supertrees.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(i=k+1;i<comp[u].size();i++){
      |             ~^~~~~~~~~~~~~~~
supertrees.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(k=0;k<comp[u].size();k++){
      |          ~^~~~~~~~~~~~~~~
supertrees.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(i=0;i<V[x].size();i++){
      |            ~^~~~~~~~~~~~
supertrees.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(i=0;i<comp[u].size();i++){
      |            ~^~~~~~~~~~~~~~~

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