제출 #1145154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145154		huutuan	Flights (JOI22_flights)	C++20	0 / 100	368 ms	590236 KiB

Ali

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

#include <bits/stdc++.h>

using namespace std;

namespace Ali{
   const int N=1e5+1;
   const int M=1429, SZ=13;
   int n;
   vector<int> g[N], g2[N];
   int sz[N], par[N], dep[N], ID[N], 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);
   }
   int dp[14];
   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].size()<2){
         g2[u].push_back(++cnt);
         ++sz[cnt];
      }else{
         if (sz[g2[u][0]]<6) dfs3(g2[u][0], id);
         else dfs3(g2[u][1], id);
      }
      ++sz[u];
   }
   int dfs4(int u){
      vector<int> vv;
      for (int v:g2[u]){
         vv.push_back(dfs4(v));
      }
      if (g2[u].empty()) return 0;
      if (g2[u].size()==1){
         return vv[0];
      }
      if (vv[0]>vv[1]){
         swap(vv[0], vv[1]);
         swap(g2[u][0], g2[u][1]);
      }
      int ans=0;
      for (int j=0; j<sz[u]-1; ++j) if (j<=sz[u]-j-1 && sz[u]-j-1<7){
         if (j==sz[g2[u][0]]){
            if (j==sz[u]-j-1){
               for (int k=0; k<vv[0]; ++k) ans+=dp[j]-k;
               ans+=vv[1]-vv[0];
            }else ans+=vv[0]*vv[1];
         }else{
            if (j==sz[u]-j-1) ans+=dp[j]*(dp[j]+1)/2;
            else ans+=dp[j]*dp[sz[u]-j-1];
         }
      }
      return ans;
   }
   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){
      memset(dp, 0, sizeof dp);
      dp[0]=1;
      dp[1]=1;
      for (int i=1; i<14; ++i){
         for (int j=0; j<i-1; ++j) if (j<=i-j-1 && i-j-1<7){
            if (j==i-j-1) dp[i]+=dp[j]*(dp[j]+1)/2;
            else dp[i]+=dp[j]*dp[i-j-1];
         }
      }
      cc.clear();
      n=_N;
      for (int i=0; i<n*2; ++i) g[i].clear(), g2[i].clear();
      for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
      dfs(0, -1);
      if (sz[0]<7) cc.emplace_back(1, 0);
      cnt=n;
      for (int i=0; i<(int)cc.size(); ++i){
         dfs2(cc[i][0], i);
         while (sz[cc[i][0]]<13) dfs3(cc[i][0], i);
         f[i]=dfs4(cc[i][0]);
         cc[i].resize(1);
         dfs2(cc[i][0], i);
      }
      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;
      }
   }
   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 val=f[gx];
         for (int i=0; i<7; ++i) ans.push_back('0'+(val>>i&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;
         int val=ID[ux]%SZ;
         val=val*66+f[gx];
         val=val*66+f[gy];
         int d=dist(ux, uy);
         val=val*10000+d;
         int lg=30;
         for (int i=0; i<lg; ++i) ans.push_back('0'+(val>>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=13;
   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;
   }
   vector<int> g[20];
   int dp[14], cnt, par[14], dep[14];
   void dfs(int u, int sz, int val){
      for (int j=0; j<sz-1; ++j) if (j<=sz-j-1 && sz-j-1<7){
         int sum=0;
         if (j==sz-j-1) sum=dp[j]*(dp[j]+1)/2;
         else sum=dp[j]*dp[sz-j-1];
         if (val>=sum) val-=sum;
         else{
            if (j==sz-j-1){
               int fx, fy;
               for (int k=0; k<=dp[j]; ++k){
                  if (val>=dp[j]-k) val-=dp[j]-k;
                  else{
                     fx=k, fy=fx+val;
                     break;
                  }
               }
               if (j){
                  ++cnt;
                  par[cnt]=u;
                  dep[cnt]=dep[u]+1;
                  g[u].push_back(cnt);
                  dfs(cnt, j, fx);
               }
               if (sz-j-1){
                  ++cnt;
                  par[cnt]=u;
                  dep[cnt]=dep[u]+1;
                  g[u].push_back(cnt);
                  dfs(cnt, sz-j-1, fy);
               }
            }else{
               int fx, fy;
               fy=val%dp[sz-j-1], fx=val/dp[sz-j-1];
               if (j){
                  ++cnt;
                  par[cnt]=u;
                  dep[cnt]=dep[u]+1;
                  g[u].push_back(cnt);
                  dfs(cnt, j, fx);
               }
               if (sz-j-1){
                  ++cnt;
                  par[cnt]=u;
                  dep[cnt]=dep[u]+1;
                  g[u].push_back(cnt);
                  dfs(cnt, sz-j-1, fy);
               }
            }
            break;
         }
      }
   }
   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;
   }
   int Answer(string T){
      memset(dp, 0, sizeof dp);
      dp[0]=1;
      dp[1]=1;
      for (int i=1; i<14; ++i){
         for (int j=0; j<i-1; ++j) if (j<=i-j-1 && i-j-1<7){
            if (j==i-j-1) dp[i]+=dp[j]*(dp[j]+1)/2;
            else dp[i]+=dp[j]*dp[i-j-1];
         }
      }
      int gx=x/SZ, gy=y/SZ;
      int ans=-1;
      if (gx==gy){
         int fx=0;
         for (int i=0; i<7; ++i) fx|=(T[i]-'0')<<i;
         cnt=0;
         for (int i=0; i<14; ++i) g[i].clear();
         dfs(0, 13, fx);
         ans=dist(x%SZ, y%SZ);
      }else{
         int val=0;
         for (int i=0; i<30; ++i) val|=(T[i]-'0')<<i;
         int ux=0, fx=0, fy=0, d=0;
         d=val%10000, val/=10000;
         fy=val%66, val/=66;
         fx=val%66, val/=66;
         ux=val;
         cnt=0;
         for (int i=0; i<14; ++i) g[i].clear();
         dfs(0, 13, fx);
         int dx=dist(ux, x%SZ);
         cnt=0;
         for (int i=0; i<14; ++i) g[i].clear();
         dfs(0, 13, fy);
         int dy=dist(0, y%SZ);
         ans=d+dx+dy;
      }
      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