제출 #305275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305275		chubyxdxd	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	273 ms	22140 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int pad[2000];
void init(int x){
  for(int i=0;i<=x;i++){
    pad[i]=i;
  }
}
int findset(int i){
  if(pad[i]==i)return i;
  return pad[i]=findset(pad[i]);
}
bool issameset(int i,int j){
  return findset(pad[i])==findset(pad[j]);
}
void unionset(int i,int j){
  pad[i]=pad[findset(j)];
}
int construct(vector<vector<int>> p) {
	int n = p.size();
	init(n);
	vector<vector<int>> answer;
	for(int i=0;i<n;i++){
	  answer.push_back(vector<int>(n,0));
	}
	int cnt=0;
	for(int i=0;i<n;i++){
	  for(int j=0;j<n;j++){
	    if(p[i][j]==1)cnt++;
	  }
	}
	int sw=1;
	if(cnt==n*n){
	  //cout<<123<<endl;
        for(int i=0;i<n-1;i++){
	  answer[i][i+1]=1;
	  answer[i+1][i]=1;
	}
	}
	else{
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]==1){
		if(!issameset(i,j)){unionset(i,j);
		}
	      }
	    }
	  }/*
	  for(int i=0;i<n;i++){
	    cout<<findset(i)<<" ";
	  }
	  cout<<endl;*/
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]==1){
		if(issameset(pad[i],pad[j])){}
		else sw=0;
		//if(sw==0)cout<<i<<" gg "<<j<<endl;
	      }
	      else{
		if(issameset(i,j))sw=0;
		//if(sw==0)cout<<i<<" gg1 "<<j<<endl;
	      }
	    }
	  }
	  vector<int> last(n,-1);
	  for(int i=0;i<n;i++){
	    if(last[findset(i)]==-1){
	      last[findset(i)]=i;
	    }
	    else{
	      answer[i][last[findset(i)]]=1;
	      answer[last[findset(i)]][i]=1;
	    }
	  }
	}
	if(sw){
	build(answer);
	return 1;}
	else return 0;

}

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