Submission #1131452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131452		huutuan	Island Hopping (JOI24_island)	C++20	65 / 100	5 ms	448 KiB

island

#include "island.h"

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> a;

int f[300][300], tr[300][300];

int dp(int l, int r){
   if (l>r) return 0;
   if (f[l][r]!=-1) return f[l][r];
   if (l==r && a[l].second==1){
      tr[l][r]=-1;
      return f[l][r]=0;
   }
   pair<int, int> res={(int)1e9, -1};
   for (int j=l; j<=r; ++j){
      res=min(res, {1+max(dp(l, j-1), dp(j+1, r)), j});
   }
   tr[l][r]=res.second;
   return f[l][r]=res.first;
}

void solve(int _N, int _L) {
   int query_count=0;
   mt19937 rng(69420);
   int n=_N;
   int root=0;
   vector<int> bfs_order{root}, pos(n);
   for (int i=1; i<n; ++i) bfs_order.push_back(query(root+1, i)-1), ++query_count;
   for (int i=0; i<n; ++i) pos[bfs_order[i]]=i;
   vector<vector<int>> child(n);
   vector<int> par(n);
   vector<int> check(n);
   for (int i=n-1; i>=1; --i){
      int u=bfs_order[i];
      sort(child[u].begin(), child[u].end());
      for (int j:child[u]) check[j]=1;
      vector<int> cnt(child[u].size()+1), save(child[u].size()+1);
      for (int j=0; j<i; ++j){
         int v=bfs_order[j];
         int t=lower_bound(child[u].begin(), child[u].end(), v)-child[u].begin();
         ++cnt[t];
         save[t]=v;
      }
      a.clear();
      for (int j=0; j<=(int)child[u].size(); ++j) if (cnt[j]){
         a.emplace_back(j, cnt[j]);
      }
      for (int j=0; j<=(int)child[u].size(); ++j) for (int k=0; k<=(int)child[u].size(); ++k){
         f[j][k]=-1;
      }
      dp(0, (int)a.size()-1);
      cerr << query_count << endl;
      if (query_count==638){
         query_count=638;
      }
      int l=0, r=a.size()-1;
      while (1){
         int mid=tr[l][r];
         int v=-1;
         if (l==r && f[l][r]==0){
            v=save[a[l].first];
         }else{
            v=query(u+1, a[mid].first+1)-1, ++query_count;
         }
         if (!check[v]){
            par[u]=v;
            child[v].push_back(u);
            break;
         }
         if (child[u][a[mid].first]==v) l=mid+1;
         else r=mid-1;
      }
      for (int j:child[u]) check[j]=0;
   }
   for (int i=0; i<n; ++i) if (i!=root) answer(i+1, par[i]+1);
}

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