oj.uz

Submission #937791

# Submission time Handle Problem Language Result Execution time Memory
937791 2024-03-04T13:14:40 Z Hugo1729 Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 600 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)groups.connect(i,j);
      }
    }
    vector<int> row;
    row.assign(n,0);
    answer.push_back(row);
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==0&&groups.same(i,j))return 0;
      }
    }
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==1&&!rep.same(i,j)){
          rep.connect(i,j);
          for(int k=0;k<n;k++){
            if(p[i][k]!=p[j][k])return 0;
          }
        }
      }
    }
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(groups.same(i,j)){
          if(p[i][j]==0)return 0;
          else if(p[i][j]==1){
            if(!rep.same(i,j))return 0;
          } else if(p[i][j]==2){
            if(rep.same(i,j))return 0;
          } else if(p[i][j]==3)return 0;
        }else{
          if(p[i][j]>0)return 0;
        }
      }
    }
  }
  vector<vector<int>> circles;
  int t=0;
  map<int,int> mcircles;
  for(int i=0;i<n;i++){
    if(rep.find(i)==i){
      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{
      answer[i][rep.find(i)]=1;
      answer[rep.find(i)][i]=1;
    }
  }

  // cout << "dsfasdfsdafsda";

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -