제출 #1284871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284871		Faisal_Saqib	Island Hopping (JOI24_island)	C++20	15 / 100	218 ms	1188 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;
int par[N];
vector<int> qry[N],nei[N];
bool want[N][N];
int get(int x)
{
  if(par[x]==x)return x;
  return par[x]=get(par[x]);
}
vector<pair<int,int>> ans;
void merge(int x,int y)
{
  int gx=x,gy=y;
  // cout<<"trying "<<x<<' '<<y<<endl;
  x=get(x);
  y=get(y);
  // cout<<"Comp "<<x<<' '<<y<<endl;
  if(x!=y){ans.push_back({gx,gy});par[x]=y;}
}
void solve(int n, int l)
{
  for(int i=1;i<=n;i++)
  {
    nei[i].clear();
    qry[i].clear();
    // cout<<"qry["<<i<<"]: ";
    for(int k=1;k<=n-1;k++)
    {
      qry[i].push_back(query(i,k));
      // cout<<qry[i].back()<<' ';
    }
    // cout<<endl;
  }
  // new algo
  for(int i=1;i<=n;i++)
  {
    par[i]=i;
  }
  for(int i=1;i<=n;i++)
  {
    merge(i,qry[i][0]); // deg[i]>0
  }
  for(int j=1;j<n-1;j++)
  {
    for(int i=1;i<=n;i++)
    {
      if(want[qry[i][j]][i])
      {
        // cout<<"Both "<<i<<' '<<qry[i][j]<<endl;
        merge(i,qry[i][j]);
      }
      // cout<<"i: "<<i<<" wants "<<qry[i][j]<<endl;
      want[i][qry[i][j]]=1;
    }
  }
  // cout<<"Final Edges"<<endl;
  for(auto x:ans)
  {
    // cout<<x.first<<' '<<x.second<<endl;
    answer(x.first,x.second);
  }
  return;
  // 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: 0 / 7
• Subtask 4: 9 / 9
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 22
• Subtask 8: 0 / 28