oj.uz

Submission #1063260

# Submission time Handle Problem Language Result Execution time Memory
1063260 2024-08-17T15:56:12 Z weajink Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 348 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxN = 1001;
int par[maxN][2];
int ssize[maxN][2];
int FIND(int x, bool ktory){
  if (par[x][ktory] == x) return x;
  return par[x][ktory] = FIND(par[x][ktory],ktory);
} 
void UNION(int x, int y,bool ktory){
  int a = FIND(x,ktory);
  int b = FIND(y,ktory);
  if (a == b) return;
  if (ssize[a][ktory] > ssize[b][ktory]) swap(a,b);
  par[a][ktory] = b;
  ssize[b][ktory] += ssize[a][ktory];
}
vector<int> cykl[maxN];
int construct(vector<vector<int> > p){
  int n = p.size();
  int i;
  for (i = 0; i < n; i++){
    par[i][0] = par[i][1] = i;
    ssize[i][0] = ssize[i][1] = 1;
  } 
  for (i = 0; i < n; i++){
    for (int j = 0; j < n-1; j++){
      if (p[i][j] == 3){
        return 0;
      }
      if (p[i][j]){
        UNION(i,j,0);
      } 
      if (p[i][j] == 1){
        UNION(i,j,1);
      } 
    }
  }
  for (i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      if (i == j) continue;
      if (!p[i][j] && FIND(i,0) == FIND(j,0)){
        return 0;
      }
      if (p[i][j] == 1 && FIND(i,1) != FIND(j,1)){
        return 0;
      }
    }
  } 
  vector<vector<int> > wy;
  wy.resize(n);
  for (i = 0; i < n; i++){
    wy[i].assign(n,0);
  }
  for (i = 0; i < n; i++){
    if (FIND(i,1) != i){
      wy[i][FIND(i,1)] = 1;    
      wy[FIND(i,1)][i] = 1;
    }else{
      cykl[FIND(i,0)].push_back(i);     
    }
  }
  for (i = 0; i < n; i++){
    if (FIND(i,0) != i) continue;
    if (cykl[i].size() == 2) return 0;
    for (int j = 0; j < (int)cykl[i].size(); j++){
      wy[cykl[i][j]][cykl[i][(j+1)%cykl[i].size()]] = 1;
      wy[cykl[i][(j+1)%cykl[i].size()]][cykl[i][j]] = 1;
    }
  }
  build(wy);
  return 1;
}

Subtask #1
0 / 11.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 #2
0 / 10.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 #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 348 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 348 KB b[0][0] is not 0
2 Halted 0 ms 0 KB -