Submission #313659

#	Time	Username	Problem	Language	Result	Execution time	Memory
313659		DanerZein	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	281 ms	26616 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef unordered_set<int> us;
int p1[1010],cc[1010];
void init(int n){
  for(int i=0;i<n;i++) p1[i]=cc[i]=i;
}
int findset(int x,int sw){
  if(sw==1){
    if(p1[x]==x) return x;
    return p1[x]=findset(p1[x],sw);
  }
  else{
    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;
    }
    else{
      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]==3) return 0;
      if(i==j){
	if(p[i][j]==2 or p[i][j]==0){ return 0;}
	continue;
      }
      if(p[i][j]!=0){
	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<<i<<": ";
    for(int j=0;j<dt[i].size();j++){
      // cout<<dt[i][j]<<" ";
       if(issameset(dt[i][j],i,2)) return 0;
    }
    // cout<<endl;
  }
  vi an;
  an.assign(n,-1);
  for(int i=0;i<n;i++){
    if(an[findset(i,1)]==-1){
      an[findset(i,1)]=i;
    }
    else{
      int a=an[findset(i,1)];
      bu[a][i]=bu[i][a]=1;
      an[findset(i,1)]=i;
    }
  }
  vector<us> ul,pr;
  ul.resize(n);
  pr.resize(n);
  for(int i=0;i<n;i++){
    pr[findset(i,2)].insert(findset(i,1));
  }
  /* for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) cout<<bu[i][j]<<" ";
    cout<<endl;
  }*/
  for(int i=0;i<n;i++){
    if(pr[i].size()==2) return 0;
    if(pr[i].empty()) continue;
    int ant=-1,pi;
    for(auto &v:pr[i]){
      if(ant==-1){
	pi=v;
	ant=v;
      }
      else{
	bu[ant][v]=bu[v][ant]=1;
	ant=v;
      }
    }
    if(pi!=ant)
    bu[pi][ant]=bu[ant][pi]=1;
  }
  build(bu);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int j=0;j<dt[i].size();j++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:104:27: warning: 'pi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |     bu[pi][ant]=bu[ant][pi]=1;
      |                           ^

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