Submission #1146465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146465		huutuan	Flights (JOI22_flights)	C++20	100 / 100	293 ms	6184 KiB

Ali

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

#include <bits/stdc++.h>

using namespace std;

namespace {
   vector<string> t6{
      "0001100111",
      "0001011011",
      "0000111011",
      "0000011111",
      "0000101111",
      "0001110011",
      "0010110011",
      "0001101101",
      "0000111101",
      "0000110111",
      "0001011101",
   };

   vector<string> t7{
      "000011100111",
      "000011011011",
      "000001101111",
      "000110110011",
      "000011011101",
   };

   vector<int>  st{0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
   vector<int> add{3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};

   vector<int> g[14], gg[14];
   int d[14], num[14], par[14];
   map<vector<int>, int> mp1, mp2;

   void clear(){
      for (int i=0; i<14; ++i) g[i].clear(), gg[i].clear();
   }

   void build(string s, int root){
      int id=0, cur=0;
      auto dfs=[&](auto &&self, int u) -> void {
         while (s[id]=='0'){
            ++id;
            ++cur;
            gg[u].push_back(cur);
            self(self, cur);
         }
         ++id;
      };
      dfs(dfs, 0);
      cur=0;
      queue<int> q;
      q.push(0);
      num[0]=cur;
      par[num[0]]=-1;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:gg[u]){
            num[v]=++cur;
            g[num[u]].push_back(num[v]);
            g[num[v]].push_back(num[u]);
            par[num[v]]=num[u];
            q.push(v);
         }
      }
      auto dfs2=[&](auto &&self, int u, int p) -> void {
         for (int v:g[u]) if (v!=p){
            d[v]=d[u]+1;
            self(self, v, u);
         }
      };
      d[root]=0;
      dfs2(dfs2, root, -1);
   }

   void gen(){
      for (int i=0; i<11; ++i){
         for (int j=st[i]; j<5; ++j){
            string t="0"+t7[j]+"10"+t6[i]+"1";
            clear();
            build(t, 0);
            vector<int> dd(d, d+14);
            if (!mp1.count(dd)) mp1[dd]=mp1.size();
         }
      }
      // cout << mp1.size() << '\n';
      set<vector<int>> tt;
      for (int i=0; i<11; ++i){
         for (int j=st[i]; j<5; ++j){
            string t="0"+t7[j]+"10"+t6[i]+"1";
            clear();
            build(t, 0);
            vector<int> ff(d, d+14);
            sort(ff.begin(), ff.end());
            for (int k=0; k<14; ++k) if ((int)g[k].size()<=2){
               clear();
               build(t, k);
               vector<int> dd(d, d+14);
               if (!mp2.count(dd)) mp2[dd]=mp2.size();
            }
         }
      }
      // cout << mp2.size() << '\n';
   }
}

namespace Ali{
   const int N=3e4+1;
   const int M=1429, SZ=14;
   int n;
   vector<int> g[N], g2[N];
   int sz[N], par[N], dep[N], ID[N], deg[N];
   string f[N];
   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;
   }
   vector<vector<int>> cc;
   void dfs(int u, int p){
      sz[u]=1;
      par[u]=p;
      dep[u]=p==-1?0:dep[p]+1;
      if (p!=-1) g[u].erase(find(g[u].begin(), g[u].end(), p));
      for (int v:g[u]) if (v!=p){
         dfs(v, u);
         if (sz[v]<7){
            g2[u].push_back(v);
            sz[u]+=sz[v];
         }
      }
      if (sz[u]>=7) cc.emplace_back(1, u);
   }
   void dfs2(int u, int id){
      if (u!=cc[id][0]) cc[id].push_back(u);
      for (int v:g2[u]){
         dfs2(v, id);
      }
   }
   int cnt;
   void dfs3(int u, int id){
      if ((int)g2[u].empty() || ((int)g2[u].size()==1 && sz[g2[u][0]]==6)){
         g2[u].push_back(++cnt);
         par[cnt]=u;
         dep[cnt]=dep[u]+1;
         ++sz[cnt];
      }else{
         if (sz[g2[u][0]]<6) dfs3(g2[u][0], id);
         else dfs3(g2[u][1], id);
      }
      ++sz[u];
   }
   void dfs4(int u){
      vector<string> vv;
      for (int v:g2[u]){
         dfs4(v);
         vv.push_back(f[v]);
      }
      if (g2[u].empty()){
         f[u]="";
         return;
      }
      if (g2[u].size()==1){
         f[u]="0"+vv[0]+"1";
         return;
      }
      if ((vv[0]<vv[1] && vv[0].size()==vv[1].size()) || (vv[0].size()<vv[1].size())){
         swap(vv[0], vv[1]);
         swap(g2[u][0], g2[u][1]);
      }
      f[u]="0"+vv[0]+"10"+vv[1]+"1";
   }
   int dist(int u, int v){
      if (dep[u]<dep[v]) swap(u, v);
      int ans=0;
      while (dep[u]>dep[v]) u=par[u], ++ans;
      while (u!=v) u=par[u], v=par[v], ans+=2;
      return ans;
   }
   void dfs_sz(int u, int p){
      sz[u]=1;
      for (int v:g[u]) if (v!=p) dfs_sz(v, u), sz[u]+=sz[v];
   }
   int find_centroid(int u, int p){
      for (int v:g[u]) if (v!=p && sz[v]*2>n) return find_centroid(v, u);
      return u;
   }
   int bfs(int cen){
      vector<int> vis(n+1);
      queue<int> q;
      q.push(cen); vis[cen]=1;
      while (q.size()){
         int u=q.front(); q.pop();
         if ((int)g[u].size()<=2) return u;
         for (int v:g[u]) if (!vis[v]){
            q.push(v);
            vis[v]=1;
         }
      }
      assert(false);
      return -1;
   }
   void init(int _N, vector<int> U, vector<int> V){
      if (mp1.empty()) gen();
      cc.clear();
      n=_N;
      for (int i=0; i<N; ++i) g[i].clear(), g2[i].clear(), sz[i]=0;
      for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]), ++deg[U[i]], ++deg[V[i]];
      dfs_sz(0, -1);
      int cen=find_centroid(0, -1);
      int root=bfs(cen);
      dfs(root, -1);
      if (sz[root]<7) cc.emplace_back(1, root);
      reverse(cc.begin(), cc.end());
      cnt=n;
      for (int i=0; i<(int)cc.size(); ++i){
         int root=cc[i][0];
         dfs2(root, i);
         while (sz[root]<13) dfs3(root, i);
         dfs4(root);
         cc[i].resize(1);
         dfs2(root, i);
         int id0=find(t6.begin(), t6.end(), f[g2[root][0]])-t6.begin();
         int id1=find(t6.begin(), t6.end(), f[g2[root][1]])-t6.begin();
         assert(id0<11 && id1<11);
         int u=cc[i][add[id0]+1];
         if (id0<id1){
            swap(g2[root][0], g2[root][1]);
            swap(id0, id1);
            u=cc[i][add[id0]+7];
         }
         g2[u].push_back(++cnt);
         par[cnt]=u;
         dep[cnt]=dep[u]+1;
         dfs4(root);
         int id=find(t7.begin(), t7.end(), f[g2[root][0]])-t7.begin();
         assert(id<5);
         vector<int> ord;
         ord.push_back(root);
         int begin=0;
         while (begin<(int)ord.size()){
            int u=ord[begin++];
            for (int v:g2[u]) ord.push_back(v);
         }
         cc[i]=ord;
         vector<int> dd;
         for (int j:cc[i]) dd.push_back(dist(j, cc[i][0]));
         assert(mp1.count(dd));
      }
      for (int i=0; i<(int)cc.size(); ++i){
         for (int j=0; j<(int)cc[i].size(); ++j) if (cc[i][j]<n) SetID(cc[i][j], i*SZ+j), ID[cc[i][j]]=i*SZ+j;
      }
   }
   int get1(int id){
      vector<int> dd;
      for (int j:cc[id]) dd.push_back(dist(cc[id][0], j));
      assert(mp1.count(dd));
      return mp1[dd];
   }
   int get2(int id, int root){
      vector<int> dd;
      for (int j:cc[id]) dd.push_back(dist(root, j));
      assert(mp2.count(dd));
      return mp2[dd];
   }
   string get_string(int num){
      string ans;
      for (int len=1; len<=24; ++len){
         if (num<(1<<len)){
            for (int j=0; j<len; ++j) ans.push_back('0'+(num>>j&1));
            return ans;
         }else num-=(1<<len);
      }
      assert(false);
      return "";
   }
   string SendA(string S){
      string ans;
      int gx=0, gy=0;
      int t=0;
      for (int i=0; i<20; ++i) t|=(S[i]-'0')<<i;
      tie(gx, gy)=get(t);
      if (gx==gy){
         int root=cc[gx][0];
         int id0=find(t7.begin(), t7.end(), f[g2[root][0]])-t7.begin();
         int id1=find(t6.begin(), t6.end(), f[g2[root][1]])-t6.begin();
         int val=0;
         for (int i=0; i<11; ++i){
            for (int j=st[i]; j<5; ++j, ++val){
               if (id1==i && j==id0){
                  ans=get_string(val);
               }
            }
         }
         assert(ans.size());
      }else{
         int ux=cc[gx][0], uy=cc[gy][0];
         int u=uy;
         while (u!=-1 && ID[u]/SZ!=gx) u=par[u];
         if (u!=-1) ux=u;
         int d=dist(ux, uy);
         if ((int)g2[ux].size()==2 && sz[g2[ux][0]]<6){
            ux=g2[ux][1];
            --d;
         }
         int val=0;
         if (d>=5020){
            val=get1(gx);
            val=val*((int)mp1.size())+get1(gy);
            val=val*5020+(d-5020);
            val+=((int)mp2.size())*((int)mp1.size())*5020;
         }else{
            val=get2(gx, ux);
            val=val*((int)mp1.size())+get1(gy);
            val=val*5020+d;
         }
         val+=28;
         ans=get_string(val);
      }
      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 {
   vector<string> t6{
      "0001100111",
      "0001011011",
      "0000111011",
      "0000011111",
      "0000101111",
      "0001110011",
      "0010110011",
      "0001101101",
      "0000111101",
      "0000110111",
      "0001011101",
   };

   vector<string> t7{
      "000011100111",
      "000011011011",
      "000001101111",
      "000110110011",
      "000011011101",
   };

   vector<int>  st{0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
   vector<int> add{3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};

   vector<int> g[14], gg[14];
   int d[14], num[14], par[14];
   map<vector<int>, int> mp1, mp2;

   void clear(){
      for (int i=0; i<14; ++i) g[i].clear(), gg[i].clear();
   }

   void build(string s, int root){
      int id=0, cur=0;
      auto dfs=[&](auto &&self, int u) -> void {
         while (s[id]=='0'){
            ++id;
            ++cur;
            gg[u].push_back(cur);
            self(self, cur);
         }
         ++id;
      };
      dfs(dfs, 0);
      cur=0;
      queue<int> q;
      q.push(0);
      num[0]=cur;
      par[num[0]]=-1;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:gg[u]){
            num[v]=++cur;
            g[num[u]].push_back(num[v]);
            g[num[v]].push_back(num[u]);
            par[num[v]]=num[u];
            q.push(v);
         }
      }
      auto dfs2=[&](auto &&self, int u, int p) -> void {
         for (int v:g[u]) if (v!=p){
            d[v]=d[u]+1;
            self(self, v, u);
         }
      };
      d[root]=0;
      dfs2(dfs2, root, -1);
   }

   void gen(){
      for (int i=0; i<11; ++i){
         for (int j=st[i]; j<5; ++j){
            string t="0"+t7[j]+"10"+t6[i]+"1";
            clear();
            build(t, 0);
            vector<int> dd(d, d+14);
            if (!mp1.count(dd)) mp1[dd]=mp1.size();
         }
      }
      // cout << mp1.size() << '\n';
      set<vector<int>> tt;
      for (int i=0; i<11; ++i){
         for (int j=st[i]; j<5; ++j){
            string t="0"+t7[j]+"10"+t6[i]+"1";
            clear();
            build(t, 0);
            vector<int> ff(d, d+14);
            sort(ff.begin(), ff.end());
            for (int k=0; k<14; ++k) if ((int)g[k].size()<=2){
               clear();
               build(t, k);
               vector<int> dd(d, d+14);
               if (!mp2.count(dd)) mp2[dd]=mp2.size();
            }
         }
      }
      // cout << mp2.size() << '\n';
   }
}

namespace Benjamin{
   const int M=1429, SZ=14;
   int n, x, y;
   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);
      int gx=x/SZ, gy=y/SZ;
      int t=get({gx, gy});
      string ans;
      for (int i=0; i<20; ++i) ans.push_back('0'+(t>>i&1));
      return ans;
   }
   int dist(int u, int v){
      if (d[u]<d[v]) swap(u, v);
      int ans=0;
      while (d[u]>d[v]) u=par[u], ++ans;
      while (u!=v) u=par[u], v=par[v], ans+=2;
      return ans;
   }
   vector<int> find1(int id){
      assert(id<(int)mp1.size());
      for (auto &i:mp1) if (i.second==id) return i.first;
      assert(false);
      return {};
   }
   vector<int> find2(int id){
      assert(id<(int)mp2.size());
      for (auto &i:mp2) if (i.second==id) return i.first;
      assert(false);
      return {};
   }
   int get_number(string s){
      int ans=0;
      for (int len=1; len<(int)s.size(); ++len) ans+=1<<len;
      for (int j=0; j<(int)s.size(); ++j) ans+=(s[j]-'0')<<j;
      return ans;
   }
   int Answer(string T){
      if (mp1.empty()) gen();
      int gx=x/SZ, gy=y/SZ;
      int ans=-1;
      int val=get_number(T);
      if (gx==gy){
         int val2=0, id0=-1, id1=-1;
         for (int i=0; i<11; ++i){
            for (int j=st[i]; j<5; ++j, ++val2){
               if (val2==val){
                  id0=j, id1=i;
               }
            }
         }
         string t="0"+t7[id0]+"10"+t6[id1]+"1";
         clear();
         build(t, 0);
         ans=dist(x%SZ, y%SZ);
      }else{
         val-=28;
         if (val>=((int)mp2.size())*((int)mp1.size())*5020){
            val-=((int)mp2.size())*((int)mp1.size())*5020;
            int d=val%5020+5020; val/=5020;
            int idy=val%((int)mp1.size()); val/=(int)mp1.size();
            int idx=val;
            vector<int> dx=find1(idx);
            vector<int> dy=find1(idy);
            ans=d+dx[x%SZ]+dy[y%SZ];
         }else{
            int d=val%5020; val/=5020;
            int idy=val%((int)mp1.size()); val/=(int)mp1.size();
            int idx=val;
            vector<int> dx=find2(idx);
            vector<int> dy=find1(idy);
            ans=d+dx[x%SZ]+dy[y%SZ];
         }
      }
      return ans;
   }
}

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: 85 / 85