Submission #313270

#	Time	Username	Problem	Language	Result	Execution time	Memory
313270		DanerZein	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int pa[1010],tam[1010];
void init(int n){
  for(int i=0;i<n;i++) {pa[i]=i;
    tam[i]=1;}
}
int findset(int x){
  if(pa[x]==x) return x;
  return pa[x]=findset(pa[x]);
 }
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int x=findset(i),y=findset(j);
    pa[x]=y;
    tam[y]+=tam[x];
  }
}
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(i==j){
	if(p[i][j]==0 or p[i][j]==2) return 0;
	continue;
      }
      if(p[i][j]==2){
	unionset(i,j);
      }
      else{
	dt[i].push_back(j);
	dt[j].push_back(i);
      }
    }
  }
  for(int i=0;i<dt.size();i++){
    for(int j=0;j<dt[i].size();j++){
      if(issameset(i,dt[i][j])){
	return 0;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(tam[findset(i)]==2){
      return 0;
    }
  }
  vi in;
  vi ant;
  in.assign(n,-1);
  ant.assign(n,-1);
  for(int i=0;i<n;i++){
    if(ant[findset(i)]==-1){
      ant[findset(i)]=i;
      in[findset(i)]=i;
    }
    else{
      int a=ant[findset(i)];
      bu[a][i]=bu[i][a]=1;
      ant[findset(i)]=i;
    }
  }
  for(int i=0;i<ant.size();i++){
    if(ant[i]!=-1){
      bu[ant[i]][in[i]]=bu[in[i]][ant[i]]=1;
    }
  }
  build(bu);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<dt.size();i++){
      |               ~^~~~~~~~~~
supertrees.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int j=0;j<dt[i].size();j++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i=0;i<ant.size();i++){
      |               ~^~~~~~~~~~~

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