Submission #313344

#	Time	Username	Problem	Language	Result	Execution time	Memory
313344		DanerZein	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1095 ms	256 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int p1[1010],tam[1010],cc[1010];
void init(int n){
  for(int i=0;i<n;i++){
    p1[i]=i;
    cc[i]=i;
    tam[i]=1;
  }
}
int findset(int x,int sw){
  if(sw==1){
    if(p1[x]==x) return x;
    return p1[x]=findset(p1[x],sw);
  }
  if(sw==2){
    if(cc[x]==x) return x;
    return cc[x]=findset(cc[x],sw);
  }
 }
bool issameset(int i,int j,int sw){
  return findset(i,sw)==findset(j,sw);
}
void unionset(int i,int j,int sw){
  if(!issameset(i,j,sw)){
    int x=findset(i,sw),y=findset(j,sw);
    if(sw==1){
      p1[x]=y;
      tam[y]+=tam[x];
    }
    if(sw==2){
      cc[x]=y;
    }
  }
}
int construct(std::vector<std::vector<int>> p) {
  vector<vi> bu;
  vector<vi> dt;
  int n=p.size();
  bu.resize(n);
  dt.resize(n);
  init(n);
  for(int i=0;i<n;i++) for(int j=0;j<n;j++) bu[i].push_back(0);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(p[i][j]!=p[j][i]) return 0;
      if(i==j){
	if(p[i][j]==0 or p[i][j]==2) return 0;
	continue;
      }
      if(p[i][j]==2 or p[i][j]==1){
	if(p[i][j]==1)unionset(i,j,1);
	unionset(i,j,2);
      }
      else{
	dt[i].push_back(j);
	dt[j].push_back(i);
      }
    }
  }
  /*for(int i=0;i<n;i++) cout<<p1[findset(i,1)]<<" ";
  cout<<endl;
  for(int i=0;i<n;i++) cout<<cc[findset(i,2)]<<" ";
  cout<<endl;*/
  /* for(int i=0;i<dt.size();i++){
    for(int j=0;j<dt[i].size();j++){
      if(issameset(i,dt[i][j],1) or issameset(i,dt[i][j],2)){
	return 0;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(tam[findset(i,2)]==2){
      return 0;
    }
  }*/
  vi in,ul;
  in.assign(n,-1);
  ul.assign(n,-1);
  for(int i=0;i<n;i++){
    if(in[findset(i,1)]==-1){
      in[findset(i,1)]=i;
      ul[findset(i,1)]=i;
    }
    else{
      int a=in[findset(i,1)];
      bu[a][i]=bu[i][a]=1;
      ul[findset(i,1)]=1;
    }
  }
  set<int> s;
  for(int i=0;i<n;i++) s.insert(findset(i,2));
  /*for(int i=0;i<n;i++) cout<<in[findset(i,1)]<<" ";
  cout<<endl;
  for(int i=0;i<n;i++) cout<<ul[findset(i,1)]<<" ";
  cout<<endl;*/
  for(auto &v:s){
    set<int> c1,c2;
    for(int i=0;i<n;i++){
      if(findset(i,2)==v){
	if(tam[findset(i,1)]!=1)c1.insert(findset(i,1));
	else c2.insert(i);
      }
    }
    /*for(auto &j:c1) cout<<j<<" ";
    cout<<endl;
    for(auto &j:c2) cout<<j<<" ";
    cout<<endl;*/
    auto it=c1.begin();
    int ant=ul[findset((*it),1)];
    for(auto &j:c2){
      bu[ant][j]=bu[j][ant]=1;
      ant=j;
    }
    it++;
    int aux;
    if(it==c1.end()){
      aux=ant;
    }
    else{
      aux=in[findset((*it),1)];
    }
    ant=ul[findset((*c1.begin()),1)];
    bu[ant][aux]=bu[aux][ant]=1;
  }
  build(bu);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int findset(int, int)':
supertrees.cpp:22:2: warning: control reaches end of non-void function [-Wreturn-type]
   22 |  }
      |  ^

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