oj.uz

Submission #937762

# Submission time Handle Problem Language Result Execution time Memory
937762 2024-03-04T12:42:38 Z Hugo1729 Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 500 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

struct DSU{
int n;
vector<int> e;

DSU(int s){
  n=s;e.assign(n,-1);
}
int find(int v){
  return (e[v]<0?v:e[v]=find(e[v]));
}
bool same(int a, int b){
  return find(a)==find(b);
}
bool connect(int a, int b){
  a=find(a);b=find(b);
  if(a==b)return 0;
  if(e[a]>e[b])swap(a,b);
  e[a]+=e[b];
  e[b]=a;
  return 1;
}
};

int construct(vector<vector<int>> p) {
  int n = p.size();
  DSU groups(n),rep(n);
  vector<vector<int>> answer;
  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==0){
          if(groups.same(i,j))return 0;
        }else if(p[i][j]==1){
          if(!rep.same(i,j)){
            bool flag=1;
            for(int k=0;k<n;k++){
              if(p[i][k]!=p[j][k]){
                flag=0;
              }
            }
            if(flag){
              rep.connect(i,j);
              groups.connect(i,j);
            } else{
              return 0;
            }
          }
        } else if(p[i][j]==2){
          if(rep.same(i,j))return 0;
          groups.connect(i,j);
        }
      }
    }
    vector<int> row;
    row.assign(n,0);
    answer.push_back(row);
  }

  vector<vector<int>> circles;
  int t=0;
  map<int,int> mcircles;
  for(int i=0;i<n;i++){
    if(rep.e[i]<0){
      if(mcircles.count(groups.find(i))==0){
        circles.push_back({rep.find(i)});
        mcircles[groups.find(i)]=t;
        t++;
      } else{
        circles[mcircles[groups.find(i)]].push_back(rep.find(i));
      }
    }else{
      if(rep.find(i)!=i){
        answer[i][rep.find(i)]=1;
        answer[rep.find(i)][i]=1;
      }
    }
  }

  // cout << "dsfasdfsdafsda";

  for(vector<int> h : circles){
    if(h.size()<=1){
      for(int i=0;i<n;i++){
        if(p[h[0]][i]>=1)return 0;
      }
      continue;
    }
    if(h.size()==2)return 0;
    
    for(int j=0;j<h.size();j++){
      answer[h[j]][h[(j+1)%h.size()]]=1;
      answer[h[(j+1)%h.size()]][h[j]]=1;
      cout << h[j] << '\n';
    }
  }
  
  build(answer);
  return 1;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -