제출 #305299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305299		chubyxdxd	슈퍼트리 잇기 (IOI20_supertrees)	C++17	75 / 100	332 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int pad[2000];
int last[2000];
int vis[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){
  if(!issameset(i,j))
    pad[findset(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;
	int pp=0;
	int p1=0;
	for(int i=0;i<n;i++){
	  for(int j=0;j<n;j++){
	    if(p[i][j]==1)cnt++;
	    if(p[i][j]==1 and i!=j)p1++;
	    if(p[i][j]==2)pp++;
	  }
	}
	int sw=1;
	if(cnt==n*n){
        for(int i=0;i<n-1;i++){
	  answer[i][i+1]=1;
	  answer[i+1][i]=1;
	}
	if(sw){
	build(answer);
	return 1;}
	else return 0;
	}
	if(p1==0){
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]!=0){
		if(!issameset(i,j)){unionset(i,j);
		}
	      }
	    }
	  }
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]!=0){
		if(issameset(pad[i],pad[j])){}
		else sw=0;
	      }
	      else{
		if(issameset(i,j))sw=0;
	      }
	    }
	  }
	  map<int,vector<int>> mp;
	  for(int i=0;i<n;i++){
	    mp[findset(i)].push_back(i);
	  }
	  for(auto it=mp.begin();it!=mp.end();it++){
	    vector<int> aux;
	    aux=(*it).second;
	    int tm=aux.size();
	    if(aux.size()==2)sw=0;
	    for(int i=0;i<tm-1;i++){
	      answer[aux[i]][aux[i+1]]=1;
	      answer[aux[i+1]][aux[i]]=1;
	    }
	    if(aux.size()!=1){
	    answer[aux[0]][aux[tm-1]]=1;
	    answer[aux[tm-1]][aux[0]]=1;}
	  }
	  	if(sw){
	build(answer);
	return 1;}
	else return 0;
	  }
	if(pp==0){
	  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++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]==1){
		if(issameset(pad[i],pad[j])){}
		else sw=0;
	      }
	      else{
		if(issameset(i,j))sw=0;
	      }
	    }
	  }
	  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;
	}
	else{
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]==1){
		unionset(i,j);
	      }
	    }
	  }
	  for(int i=0;i<n+1;i++)vis[i]=0;
	  map<int,vector<int>> mp;
	  for(int i=0;i<n;i++){
	    mp[findset(i)].push_back(i);
	  }
	  for(auto it=mp.begin();it!=mp.end();it++){
	    vector<int> aux;
	    aux=(*it).second;
	    int tm=aux.size();
	    for(int i=0;i<tm-1;i++){
	      vis[aux[i]]=1;
	      answer[aux[i]][aux[i+1]]=1;
	      answer[aux[i+1]][aux[i]]=1;
	    }
	    mp[(*it).first].clear();
	  }
	  /*for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      cout<<answer[i][j]<<" ";
	    }
	    cout<<endl;
	    }*/
	  for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	      if(p[i][j]==2){
		unionset(i,j);
	      }
	    }
	  }
	  for(int i=0;i<n;i++){
	    if(vis[i]==0){
	      mp[findset(i)].push_back(i);
	    }
	  }
	  for(auto it=mp.begin();it!=mp.end();it++){
	    vector<int> aux;
	    aux=(*it).second;
	    int tm=aux.size();
	    for(int i=0;i<tm-1;i++){
	      vis[aux[i]]=1;
	      answer[aux[i]][aux[i+1]]=1;
	      answer[aux[i+1]][aux[i]]=1;
	    }
	    if(tm>=2){
	      answer[aux[0]][aux[tm-1]]=1;
	      answer[aux[tm-1]][aux[0]]=1;
	    }
	  }}
	if(sw){
	build(answer);
	return 1;}
	else return 0;

}

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