Submission #305287

#	Time	Username	Problem	Language	Result	Execution time	Memory
305287		chubyxdxd	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	249 ms	22180 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[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]==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;
	    }
	    last[(*it).first]=aux[tm-1];
	    mp[(*it).first].clear();
	  }
	  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: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4