답안 #362555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362555	2021-02-03T16:17:03 Z	mosiashvililuka	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	1 ms	620 KB

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++){
			va.push_back(B[i][j]);
		}
		ans.push_back(va);
	}
	build(ans);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(j=0; j<vv[i].size(); j++){
      |             ~^~~~~~~~~~~~~
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
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Runtime error	1 ms	620 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Runtime error	1 ms	620 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Incorrect	1 ms	364 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-