Submission #1284836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284836		Faisal_Saqib	Island Hopping (JOI24_island)	C++20	35 / 100	219 ms	976 KiB

island

/*#include "island.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int NASA=1000;
// vector<int> qry[N];
bool vis[NASA];
int limit_n;
set<pair<ll,ll>> edg;
void dfs(int x,int p=-1)
{
  vis[x]=1;
  // int sz=1;
  for(int k=1;k<=limit_n-1;k++)
  {
    int y=query(x,k);
    // cout<<"Queried "<<x<<' '<<k<<" got y: "<<y<<" vis: "<<vis[y]<<endl;
    if(y==p)continue; // dont break on trying to visit parent
    if(vis[y])break; // one of the grand child hehe!
    // fuck maybe grand child does not exist
    if(x<y)
    {
      edg.insert({x,y});
    }
    else{
      edg.insert({y,x});
    }
    dfs(y,x);
  }
}
void solve(int n, int l)
{
  limit_n=n;
  for(int i=1;i<=n;i++)vis[i]=0;
  edg.clear();
  dfs(1);

  // for(int i=1;i<=n;i++)
  // {
  //   qry[i].clear();
  //   for(int k=1;k<=min(l/n,n-1);k++)
  //   {
  //     qry[i].push_back(query(i,k));
  //   }
  // }
  // // neighbour of a vertex are a prefix of it qry vector
  // set<pair<int,int>> edge;
  // for(int i=1;i<=n;i++)
  // {
  //   set<ll> cur;
  //   for(auto j:qry[i])
  //   {
  //     if(cur.find(j)!=cur.end())
  //     {
  //       break; // grandchild reached
  //     }
  //     if(i<j)
  //     {
  //       edge.insert({i,j});
  //     }
  //     else
  //     {
  //       edge.insert({j,i});
  //     }
  //     for(auto k:qry[j])
  //     {
  //       if(k!=i)
  //       {
  //         cur.insert(k);
  //         break;
  //       }
  //     }
  //   }
  // }
  if(edg.size()<(n-1))
  {
    exit(-1);
  }
  for(auto x:edg)
  {
    answer(x.first,x.second);
  }
}*/
// /*
#include "island.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=500;
vector<int> qry[N],nei[N];
void solve(int n, int l)
{
  for(int i=1;i<=n;i++)
  {
    nei[i].clear();
    qry[i].clear();
    for(int k=1;k<=min(l/n,n-1);k++)
    {
      qry[i].push_back(query(i,k));
    }
  }
  // neighbour of a vertex are a prefix of it qry vector
  // grand childeren are subarray
  // same goes on 
  // level-wise of tree when root is i is equal to qry[i]
  set<pair<int,int>> edge;
  for(int i=1;i<=n;i++)
  {
    set<ll> cur;
    for(auto j:qry[i])
    {
      if(cur.find(j)!=cur.end())
      {
        break; // grandchild reached
      }
      if(i<j)
      {
        nei[i].push_back(j);
        nei[j].push_back(i);
        edge.insert({i,j});
      }
      else
      {
        nei[i].push_back(j);
        nei[j].push_back(i);
        edge.insert({j,i});
      }
      for(auto k:qry[j])
      {
        if(k!=i)
        {
          cur.insert(k);
          break;
        }
      }
    }
  }
  if(edge.size()<(n-1))
  {
      for(int i=1;i<=n;i++)
      {
        set<ll> cur;
        for(auto j:qry[i])
        {
          if(cur.find(j)!=cur.end())
          {
            break; // grandchild reached
          }
          if(i<j)
          {
            // nei[i].push_back(j);
            // nei[j].push_back(i);
            edge.insert({i,j});
          }
          else
          {
            // nei[i].push_back(j);
            // nei[j].push_back(i);
            edge.insert({j,i});
          }
          for(auto k:nei[j]) // neighhbours of j such that they for sure have edge
          {
            cur.insert(k);
          }
          // for(auto k:qry[j])
          // {
          //   if(k!=i)
          //   {
          //     cur.insert(k);
          //     break;
          //   }
          // }
        }
      }
  }
  for(auto x:edge)
  {
    answer(x.first,x.second);
  }
}
// */

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 9 / 9
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 22
• Subtask 8: 0 / 28