Submission #305282

#	Time	Username	Problem	Language	Result	Execution time	Memory
305282		chubyxdxd	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	274 ms	22264 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;
	int pp=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]==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(pp!=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(cnt!=n*n and 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;

}

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