Submission #1143398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143398		CDuong	Flights (JOI22_flights)	C++17	33 / 100	171 ms	4000 KiB

Ali

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

#include <bits/stdc++.h>

using namespace std;

namespace Ali{
   int n;
   vector<vector<int>> g;
   vector<int> tour, tin, tout, dep;
   vector<vector<int>> st;
   void dfs(int u, int p){
      tour.push_back(u);
      tin[u]=(int)tour.size()-1;
      for (int v:g[u]) if (v!=p) dep[v]=dep[u]+1, dfs(v, u), tour.push_back(u);
      tout[u]=(int)tour.size()-1;
   }
   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;
      g.clear(), tour.clear(), tin.clear(), tout.clear(), dep.clear(), st.clear();
      g.resize(n);
      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); tout.resize(n); dep.resize(n);
      dfs(0, -1);
      int lg=__lg((n*2-1)*2-1);
      st.assign(lg, vector<int>(n*2-1));
      for (int i=0; i<n*2-1; ++i) st[0][i]=dep[tour[i]];
      for (int i=1; i<lg; ++i){
         for (int j=0; j+(1<<i)-1<n*2-1; ++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]);
   }
   string SendA(string S){
      int lg=__lg((n*2-1)*2-1);
      int x=0;
      for (int i=0; i<lg; ++i) x|=(S[i]-'0')<<i;
      x=tour[x];
      int rem=20-lg;
      int size=(n*2-1+(1<<rem)-1)>>rem;
      int id=0;
      for (int i=0; i<rem; ++i) id|=(S[i+lg]-'0')<<i;
      lg=__lg(n*2-1);
      string ans;
      int d=dist(x, tour[id*size]);
      for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
      for (int i=id*size+1; i<(id+1)*size && i<n*2-1; ++i){
         int nd=dist(x, tour[i]);
         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;
   string SendB(int N, int X, int Y){
      n=N, x=X, y=Y;
      if (x>y) swap(x, y);
      int lg=__lg((n*2-1)*2-1);
      string ans;
      for (int i=0; i<lg; ++i) ans.push_back('0'+(x>>i&1));
      int rem=20-lg;
      int size=(n*2-1+(1<<rem)-1)>>rem;
      int id=y/size;
      for (int i=0; i<rem; ++i) ans.push_back('0'+(id>>i&1));
      return ans;
   }
   int Answer(string T){
      int lg=__lg((n*2-1)*2-1);
      int rem=20-lg;
      int size=(n*2-1+(1<<rem)-1)>>rem;
      int id=y/size;
      int idy=y-(id*size);
      lg=__lg(n*2-1);
      int d=0;
      for (int i=0; i<lg; ++i) d|=(T[i]-'0')<<i;
      for (int i=0; i+lg<=(int)T.size(); ++i){
         if (idy==i) return d;
         int nd=d+(T[i+lg]=='1'?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: 18 / 85