제출 #309552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309552		algorithm16	슈퍼트리 잇기 (IOI20_supertrees)	C++14	40 / 100	267 ms	22392 KiB

supertrees

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include "supertrees.h"
using namespace std;
int parent[1005],d[1005];
vector <vector<int> > sol;
set <int> s1;
vector <int> v1;
int find_par(int x) {
	if(parent[x]==x) return x;
	int par=find_par(parent[x]);
	parent[x]=par;
	return par;
}
void s(int x,int y) {
	if(find_par(x)==find_par(y)) return;
	sol[x][y]=1;
	sol[y][x]=1;
	x=find_par(x);
	y=find_par(y);
	if(x==y) return;
	if(d[x]==d[y]) d[x]+=1;
	if(d[x]>d[y]) parent[y]=x;
	else parent[x]=y;
}
int construct(vector <vector<int> > p) {
	int n=p.size(),maxi=0;
	for(int i=0;i<n;i++) {
		parent[i]=i;
		d[i]=1;
		sol.push_back(v1);
		for(int j=0;j<n;j++) {
			sol[i].push_back(0);
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(i==j) continue;
			if(p[i][j]==1) s(i,j);
			maxi=max(maxi,p[i][j]);
		}
	}
	if(maxi>2) return 0;
	if(n==2 && maxi>1) return 0;
	/*for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cout << sol[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/
	vector <int> v;
	for(int i=0;i<n;i++) {
		v.clear();
		for(int j=0;j<n;j++) {
			if(p[i][j]==2) v.push_back(j);
		}
		if(v.empty()) continue;
		if(v.size()==1) return 0;
		/*for(int j=0;j<v.size();j++) {
			cout << v[j] << " ";
		}
		cout << "\n";*/
		s(i,v[0]);
		for(int j=0;j<v.size()-1;j++) {
			s(v[j],v[j+1]);
		}
		if(s1.find(find_par(i))!=s1.end()) continue;
		s1.insert(find_par(i));
		sol[i][v.back()]=1;
		sol[v.back()][i]=1;
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(i==j) continue;
			if(find_par(i)==find_par(j) && p[i][j]==0) return 0;
		}
	}
	build(sol);
	return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j=0;j<v.size()-1;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