Submission #1062358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062358		sleepntsheep	Flights (JOI22_flights)	C++17	15 / 100	6 ms	2400 KiB

Ali

#include "Ali.h"
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

namespace {
  const int N=20000;
  std::vector<int> g[N];
  int hld[N],par[N],sz[N],dep[N];
  void dfs(int u,int p){
    dep[u]=dep[par[u]=p]+1;int best=0;
    sz[u]=1;for(auto &v:g[u])if(v-p){
      dfs(v,u),sz[u]+=sz[v];
      if(sz[v]>best)swap(v,g[u][0]),best=sz[v];
    }
  }
  void efs(int u){
    for(auto v:g[u])if(v-par[u])
      hld[v]=(v==g[u][0])?hld[u]:v,efs(v);
  }
  int lca(int u,int v){
    while(hld[u]-hld[v]){
      if(dep[hld[u]]<dep[hld[v]])swap(u,v);
      u=par[hld[u]];
    }
    return dep[u]<dep[v]?u:v;
  }
  int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
  void write(string&s,int i,int x,int b=14){
    for(int j=0;j<b;++j) s[i+j]=((x>>j)&1)+'0';
  }
}


void Init(int N, std::vector<int> U, std::vector<int> V) {
  for(int i=0;i<N;++i)g[i].clear(),hld[i]=0,par[i]=0,sz[i]=0,dep[i]=0;
  for (int i = 0; i < N; ++i) SetID(i, i);
  for(int i=0;i+1<N;++i)g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
  dfs(0,0);
  hld[0]=0;efs(0);
}

std::string SendA(std::string S) {
  string T(4128,'0');
  int X = 0, Y6 = 0;
  for(int i=0;i<14;++i)X|=((S[i]-'0')<<i);
  for(int j=0,i=14;i<20;++i,++j)Y6|=((S[i]-'0')<<j);
  for(int j=0;j<256;++j){
    int Y=Y6 | (j << 6);
    if (Y<N)
      write(T,j*14,dist(X,Y));
  }
  return T;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>
using namespace std;

namespace {
  void write(string&s,int i,int x,int b=14){
    for(int j=0;j<b;++j) s[i+j]=((x>>j)&1)+'0';
  }
  int read(string&s,int i,int b=14){
    int z=0;
    for(int j=0;j<b;++j)z|=((s[i+j]-'0'))<<j;
    return z;
  }
  int YY;
}


std::string SendB(int N, int X, int Y) {
  string S(20,'0');
  write(S,0,X);
  write(S,14,Y,6);
  YY=Y;
  return S;
}

int Answer(std::string T) {
  return read(T,(YY>>6)*14);
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85