Submission #1063261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063261		weajink	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	161 ms	24188 KiB

supertrees

#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;
    if (cykl[i].size() == 1) continue;
    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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4