제출 #1284820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284820		Faisal_Saqib	Island Hopping (JOI24_island)	C++20	2 / 100	4 ms	432 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) // worst case n^2
{
  vis[x]=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!
    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);
  }
}

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