제출 #362565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362565		mosiashvililuka	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	251 ms	26092 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int a,c,d,e,i,j,ii,jj,zx,xc,msh1[1009],zm1[1009],msh2[1009],zm2[1009];
int bo[1009],k[1009][1009],cnt;
int B[1009][1009];
vector <int> v[1009],vv[1009];
vector <vector <int> > ans;
int fnd1(int q){
	if(msh1[q]==q) return q; else msh1[q]=fnd1(msh1[q]);
}
void mrg1(int q, int w){
	q=fnd1(q);w=fnd1(w);
	if(q==w) return;
	if(zm1[q]<zm1[w]) swap(q,w);
	msh1[w]=q;
	if(zm1[q]==zm1[w]) zm1[q]++;
}
 
int fnd2(int q){
	if(msh2[q]==q) return q; else return msh2[q]=fnd2(msh2[q]);
}
void mrg2(int q, int w){
	q=fnd2(q);w=fnd2(w);
	if(q==w) return;
	if(zm2[q]<zm2[w]) swap(q,w);
	msh2[w]=q;
	if(zm2[q]==zm2[w]) zm2[q]++;
}
void dfs(int q){
	bo[q]=cnt;
	k[i][q]++;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if(bo[(*it)]==cnt) continue;
		dfs((*it));
	}
	bo[q]=0;
}
int construct(vector <vector <int> > A) {
	int a = A.size();
	for(i=0; i<a; i++){
		for(j=0; j<a; j++){
			if(A[i][j]==3){
				return 0;
			}
		}
	}
	/*for(i=0; i<a; i++){
		msh1[i]=i;zm1[i]=1;
	}
	for(i=0; i<a; i++){
		for(j=i+1; j<a; j++){
			if(A[i][j]==1){
				mrg1(i,j);
			}
		}
	}
	for(i=0; i<a; i++){
		fnd1(i);
		if(i!=msh1[i]){
			B[i][msh1[i]]=1;
			B[msh1[i]][i]=1;
			v[i].push_back(msh1[i]);
			v[msh1[i]].push_back(i);
		}
	}
	for(i=0; i<a; i++){
		msh2[i]=i;zm2[i]=1;
	}
	for(i=0; i<a; i++){
		for(j=i+1; j<a; j++){
			if(A[i][j]==2){
				mrg2(msh1[i],msh1[j]);
			}
		}
	}
	for(i=0; i<a; i++){
		fnd2(i);
		vv[msh2[i]].push_back(i);
	}
	for(i=0; i<a; i++){
		if(vv[i].size()>1){
			for(j=0; j<vv[i].size(); j++){
				jj=j-1;if(jj<0) jj=vv[i].size()-1;
				B[vv[i][j]][vv[i][jj]]=1;
				B[vv[i][jj]][vv[i][j]]=1;
				v[vv[i][j]].push_back(vv[i][jj]);
				v[vv[i][jj]].push_back(vv[i][j]);
			}
		}
	}
	for(i=0; i<a; i++){
		cnt++;
		dfs(i);
		for(j=0; j<a; j++){
			if(k[i][j]!=A[i][j]){
				return 0;
			}
		}
	}*/
	for(i=0; i<a; i++){
		vector <int> va;
		for(j=0; j<a; j++){
          	if((i==0&&j!=0)||(i!=0&&j==0)){
              B[i][j]=1;
            }else{
              B[i][j]=0;
            }
			va.push_back(B[i][j]);
		}
		ans.push_back(va);
	}
	build(ans);
	return 1;
}

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

supertrees.cpp: In function 'int fnd1(int)':
supertrees.cpp:10:39: warning: control reaches end of non-void function [-Wreturn-type]
   10 |  if(msh1[q]==q) return q; else msh1[q]=fnd1(msh1[q]);
      |                                ~~~~~~~^~~~~~~~~~~~~~

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