Submission #1141186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141186		huutuan	Flights (JOI22_flights)	C++20	0 / 100	50 ms	6880 KiB

Ali

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

#include <bits/stdc++.h>

using namespace std;

namespace Ali{
   const int M=1429, SZ=12;
   int n;
   vector<vector<int>> g, g2;
   vector<int> par, dep, ID;
   vector<vector<int>> f;
   vector<vector<vector<int>>> tr;
   vector<vector<int>> cc;
   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;
   }
   void dfs(int u, int p){
      f[u][1]=1;
      par[u]=p;
      dep[u]=p==-1?0:dep[p]+1;
      reverse(g[u].begin(), g[u].end());
      for (int v:g[u]) if (v!=p){
         vector<int> ff(SZ+1, 1e9), gg(SZ+1, -1);
         dfs(v, u);
         for (int j=1; j<=SZ; ++j) for (int k=0; k<=SZ-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;
      }
      reverse(g[u].begin(), g[u].end());
      f[u][0]=*min_element(f[u].begin()+1, f[u].end());
   }
   void trace(int u, int i, int p, int id){
      if (i==0){
         i=min_element(f[u].begin()+1, f[u].end())-f[u].begin();
         id=cc.size();
         cc.emplace_back(1, u);
      }else cc[id].push_back(u);
      int t=tr[u].size();
      for (int v:g[u]) if (v!=p){
         --t;
         int w=tr[u][t][i];
         if (w) g2[u].push_back(v);
         trace(v, w, u, id);
         i-=w;
      }
   }
   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 init(int N, vector<int> U, vector<int> V){
      n=N;
      g.assign(n, {});
      g2.assign(n, {});
      tr.assign(n, {});
      f.assign(n, vector<int>(SZ+1, 1e9));
      cc.clear();
      for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
      par.resize(n, 0); dep.resize(n, 0); ID.resize(n, 0);
      dfs(0, -1);
      assert(f[0][0]<=1429);
      trace(0, 0, -1, -1);
      for (int i=0; i<(int)cc.size(); ++i){
         for (int j=0; j<(int)cc[i].size(); ++j) SetID(cc[i][j], i*SZ+j), ID[cc[i][j]]=i*SZ+j;
      }
   }
   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){
         for (int i=1; i<SZ; ++i){
            int id=i<(int)cc[gx].size()?ID[par[cc[gx][i]]]%SZ:0;
            for (int j=0; j<4; ++j){
               ans.push_back('0'+(id>>j&1));
            }
         }
      }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;
         for (int i=0; i<4; ++i) ans.push_back('0'+((ID[ux]%SZ)>>i&1));
         for (int i=0; i<SZ; ++i) if (i!=ID[ux]%SZ){
            int d=i<(int)cc[gx].size()?dist(ux, cc[gx][i]):0;
            for (int j=0; j<4; ++j) ans.push_back('0'+(d>>j&1));
         }
         for (int i=0; i<SZ; ++i) if (i!=ID[uy]%SZ){
            int d=i<(int)cc[gy].size()?dist(uy, cc[gy][i]):0;
            for (int j=0; j<4; ++j) ans.push_back('0'+(d>>j&1));
         }
         int d=dist(ux, uy);
         int lg=__lg(n*2-1);
         for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
      }
      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{
   const int M=1429, SZ=12;
   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 Answer(string T){
      int gx=x/SZ, gy=y/SZ;
      int ans=-1;
      if (gx==gy){
         vector<int> par(SZ);
         par[0]=-1;
         for (int i=1; i<SZ; ++i){
            for (int j=0; j<4; ++j) par[i]|=(T[(i-1)*4+j]-'0')<<j;
         }
         vector<int> vx, vy;
         x%=SZ, y%=SZ;
         while (x!=-1) vx.push_back(x), x=par[x];
         while (y!=-1) vy.push_back(y), y=par[y];
         reverse(vx.begin(), vx.end());
         reverse(vy.begin(), vy.end());
         int id=0;
         while (id<(int)vx.size() && id<(int)vy.size() && vx[id]==vy[id]) ++id;
         ans=(int)vx.size()+(int)vy.size()-id*2;
      }else{
         int ux=0, uy=0, id=0;
         for (int i=0; i<4; ++i) ux|=(T[id++]-'0')<<i;
         x%=SZ, y%=SZ;
         int dx=0, dy=0;
         for (int i=0; i<SZ; ++i) if (i!=ux){
            int d=0;
            for (int j=0; j<4; ++j) d|=(T[id++]-'0')<<j;
            if (x==i) dx=d;
         }
         for (int i=0; i<SZ; ++i) if (i!=uy){
            int d=0;
            for (int j=0; j<4; ++j) d|=(T[id++]-'0')<<j;
            if (y==i) dy=d;
         }
         int d=0;
         int lg=__lg(n*2-1);
         for (int i=0; i<lg; ++i) d|=(T[id++]-'0')<<i;
         ans=dx+dy+d;
      }
      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: 0 / 15
• Subtask 2: 0 / 85