Submission #1246676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246676		CyberCow	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	424 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v[300];

int p[300], sz[300];

int p1[300], sz1[300];

int qan = 0;

//
void make_set1(int i)
{
  p1[i] = i;
  sz1[i] = 1;
}

int get_papa1(int i)
{
  if(p1[i] == i)return i;
  return p1[i] = get_papa1(p1[i]);
}

void union_set1(int a, int b)
{
  a = get_papa1(a);
  b = get_papa1(b);
  if(a == b)return;
  if(sz1[a] > sz1[b])swap(a, b);
  p1[a] = b;
  sz1[b] += sz1[a];
}
//

void make_set(int i)
{
  p[i] = i;
  sz[i] = 1;
  qan++;
}

int get_papa(int i)
{
  if(p[i] == i)return i;
  return p[i] = get_papa(p[i]);
}

void union_set(int a, int b)
{
  a = get_papa(a);
  b = get_papa(b);
  if(a == b)return;
  if(sz[a] > sz[b])swap(a, b);
  p[a] = b;
  sz[b] += sz[a];
  qan--;
}

int NN;

vector<int> XX, YY;

int perform_experimentQ(vector<int> &a)
{
  int x = perform_experiment(a); 
  qan = 0;
  for (int i = 0; i < a.size(); i++)
  {
    if(a[i] == NN)
    {
      make_set(i);
    }
  }
  for (int i = 0; i < XX.size(); i++)
  {
    if(a[XX[i]] == NN && a[YY[i]] == NN)
    {
      union_set(XX[i], YY[i]);
    }
  }
  return x - qan;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  XX = X;
  YY = Y;
  NN = N;
  // if(N <= 50)
  // {
  //   vector<int> G(N, 0);
  // vector<int> E(N, N);
  // for (int i = 0; i < X.size(); i++)
  // {
  //   v[X[i]].push_back(Y[i]);
  //   v[Y[i]].push_back(X[i]);
  // }
  // for (int i = 0; i < N; i++)
  // {             
  //   E[i] = 0;
  //   E[v[i][0]] = 0;
  //   int x = perform_experiment(E);
  //   for (int j = 0; j < N; j++)
  //   {
  //     E[i] = -1;
  //     E[v[i][0]] = j;
  //     int y = perform_experiment(E);
  //     if(x == y)
  //     {
  //       G[i] = j;
  //       break;;
  //     }
  //   }
  //   E[i] = N;
  //   E[v[i][0]] = N;
  // }
  // return G;
  // }
  vector<int> harc(N, N);
  vector<int> bi;
  for (int i = 0; i < N; i++)
  {
    make_set1(i);
    harc[i] = -1;
    if(i == 0)
    bi.push_back(1);
    else
    bi.push_back(perform_experimentQ(harc));
  }
  int ne = 1;
  vector<int> ans;
  for (int i = 1; i < N; i++)
  {
      int l = 0, r = i - 1, anss = -1;
      while(l <= r)
      {
        int m = (l + r) / 2;
        vector<int> blblb(N, N);
        for (int j = 0; j <= m; j++)
        {
          blblb[j] = -1;
        }
        blblb[i] = -1;
        int x = perform_experimentQ(blblb);
        if(x == bi[m])
        {
          anss= m;
          r = m - 1;
        }
        else
        l = m + 1;
      }
      if(anss != -1)
        union_set1(i, anss);
  }
  for (int i = 0; i < N; i++)
  {
    ans.push_back(get_papa(i));
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36