Submission #1140846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140846		huutuan	Flights (JOI22_flights)	C++20	15 / 100	301 ms	8216 KiB

Ali

#include "Ali.h"
#include <string>
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Ali{
   const int MX=15;
   int n, m;
   vector<vector<int>> g;
   vector<int> tour, tin, tout, dep;
   vector<vector<int>> st;
   vector<vector<int>> f;
   vector<vector<vector<int>>> tr;
   void dfs(int u, int p){
      tour.push_back(u);
      tin[u]=(int)tour.size()-1;
      f[u][1]=1;
      for (int v:g[u]) if (v!=p){
         vector<int> ff(MX+1, 1e9), gg(MX+1, -1);
         dep[v]=dep[u]+1;
         dfs(v, u);
         tour.push_back(u);
         for (int j=1; j<=MX; ++j) for (int k=0; k<=MX-j; ++k){
            if (ff[j+k]>f[u][j]+f[v][k]-(!!k)){
               ff[j+k]=f[u][j]+f[v][k]-(!!k);
               gg[j+k]=k;
            }
         }
         tr[u].push_back(gg);
         f[u]=ff;
      }
      f[u][0]=*min_element(f[u].begin()+1, f[u].end());
      tout[u]=(int)tour.size()-1;
   }
   void trace(int u, int i, int p){
      if (i==0) i=min_element(f[u].begin()+1, f[u].end())-f[u].begin();
      int id=tr[u].size();
      for (int j=(int)g[u].size()-1; j>=0; --j) if (g[u][j]!=p){
         --id;
         int w=tr[u][id][i];
         trace(g[u][j], w, u);
         i-=w;
      }
   }
   int dist(int u, int v){
      u=tin[u], v=tin[v];
      if (u>v) swap(u, v);
      int lg=__lg(v-u+1);
      return dep[tour[u]]+dep[tour[v]]-min(st[lg][u], st[lg][v-(1<<lg)+1])*2;
   }
   void init(int N, vector<int> U, vector<int> V){
      n=N;
      m=n*2-1;
      tour.clear();
      g.assign(n, {});
      tr.assign(n, {});
      f.assign(n, vector<int>(MX+1, 1e9));
      for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
      tin.resize(n, 0); tout.resize(n, 0); dep.resize(n, 0);
      dfs(0, -1);
      assert(f[0][0]<=1024);
      int lg=__lg(m*2-1);
      st.assign(lg, vector<int>(m));
      for (int i=0; i<m; ++i) st[0][i]=dep[tour[i]];
      for (int i=1; i<lg; ++i){
         for (int j=0; j+(1<<i)-1<m; ++j) st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
      }
      for (int i=0; i<n; ++i) SetID(i, tin[i]);
   }
   pair<int, int> get(int id){
      for (int i=0; i<m; ++i){
         if (id>=m-i) id-=m-i;
         else return {i, i+id};
      }
      return {-1, -1};
   }
   int get(pair<int, int> t){
      int ans=0;
      for (int i=0; i<t.first; ++i) ans+=m-i;
      ans+=t.second-t.first;
      return ans;
   }
   string SendA(string S){
      int sum=m*(m+1)/2;
      int size=(sum+(1<<20)-1)/(1<<20);
      int id=0;
      for (int i=0; i<20; ++i) id|=(S[i]-'0')<<i;
      string ans;
      pair<int, int> tl=get(id*size);
      pair<int, int> tr=get(min(sum-1, (id+1)*size-1));
      for (int i=tr.first; i>tl.first; --i){
         int r=i==tr.first?tr.second:m-1;
         int d=0;
         for (int j=i; j<=r; ++j){
            if (j!=r){
               int nd=dist(tour[i], tour[j+1]);
               ans.push_back('0'+(d<nd));
               d=nd;
            }
         }
      }
      int r=tl.first==tr.first?tr.second:m-1;
      int lg=__lg(n*2-1);
      int d=dist(tour[tl.first], tour[tl.second]);
      for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
      for (int j=tl.second; j<=r; ++j){
         if (j!=r){
            int nd=dist(tour[tl.first], tour[j+1]);
            ans.push_back('0'+(d<nd));
            d=nd;
         }
      }
      return ans;
   }
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
   Ali::init(N, U, V);
}

std::string SendA(std::string S) {
   return Ali::SendA(S);
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>

#include <bits/stdc++.h>

using namespace std;

namespace Benjamin{
   int n, x, y, m;
   pair<int, int> get(int id){
      for (int i=0; i<m; ++i){
         if (id>=m-i) id-=m-i;
         else return {i, i+id};
      }
      return {-1, -1};
   }
   int get(pair<int, int> t){
      int ans=0;
      for (int i=0; i<t.first; ++i) ans+=m-i;
      ans+=t.second-t.first;
      return ans;
   }
   string SendB(int N, int X, int Y){
      n=N, x=X, y=Y;
      if (x>y) swap(x, y);
      m=n*2-1;
      int sum=m*(m+1)/2;
      int size=(sum+(1<<20)-1)/(1<<20);
      int id=get({x, y})/size;
      string ans;
      for (int i=0; i<20; ++i) ans.push_back('0'+(id>>i&1));
      return ans;
   }
   int Answer(string T){
      int sum=m*(m+1)/2;
      int size=(sum+(1<<20)-1)/(1<<20);
      int id=get({x, y})/size;
      pair<int, int> tl=get(id*size);
      pair<int, int> tr=get(min(sum-1, (id+1)*size-1));
      int id_ans=0;
      for (int i=tr.first; i>tl.first; --i){
         int r=i==tr.first?tr.second:m-1;
         int d=0;
         for (int j=i; j<=r; ++j){
            if (x==i && y==j) return d;
            if (j!=r){
               int nd=d+(T[id_ans++]-'0'?1:-1);
               d=nd;
            }
         }
      }
      int r=tl.first==tr.first?tr.second:m-1;
      int lg=__lg(n*2-1);
      int d=0;
      for (int i=0; i<lg; ++i) d|=(T[id_ans++]-'0')<<i;
      for (int j=tl.second; j<=r; ++j){
         if (x==tl.first && y==j) return d;
         if (j!=r){
            int nd=d+(T[id_ans++]-'0'?1:-1);
            d=nd;
         }
      }
      return -1;
   }
}

std::string SendB(int N, int X, int Y) {
   return Benjamin::SendB(N, X, Y);
}

int Answer(std::string T) {
   return Benjamin::Answer(T);
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85