제출 #1140485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140485		huutuan	Flights (JOI22_flights)	C++20	50 / 100	170 ms	3940 KiB

Ali

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

#include <bits/stdc++.h>

using namespace std;

namespace Ali{
   int n, m;
   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;
      m=n*2-1;
      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(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: 35 / 85