Submission #1062415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062415		sleepntsheep	Flights (JOI22_flights)	C++17	22 / 100	222 ms	3156 KiB

Ali

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

using ll = long long;
namespace {
  const int N=30000;
  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'; }
  ll 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 nn;
  ll valid_enc(ll enc){ return enc/10000<nn and enc%10000<nn; }
  ll XX(ll enc){return enc/10000;}
  ll YY(ll enc){return enc%10000;}
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
  ::nn = N;
  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+1<N;++i)g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
  for(int i=0;i<N;++i)SetID(i,i);
  dfs(0,0);
  hld[0]=0;efs(0);
}

std::string SendA(std::string S) {
  ll enc=read(S,0,20);
  string T(1268,'0');
  int cnt=0;
  for(ll j=0;j<(1<<7);++j){
    ll enc2 = (enc&((1<<20)-1)) | (j<<20);
    if(not valid_enc(enc2))continue;
    int xx=XX(enc2),yy=YY(enc2);
    while(cnt*14+14>=T.size())T+='0';
    write(T,cnt*14,dist(xx,yy));
    ++cnt;
  }
  return T;
}

Benjamin

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

namespace {
  void write(string&s,int i,ll x,int b=14){ for(ll j=0;j<b;++j) s[i+j]=((x>>j)&1)+'0'; }
  ll read(string&s,int i,int b=14){ int z=0; for(ll j=0;j<b;++j)z|=((s[i+j]-'0'))<<j; return z; }
  int yy,nn;
  ll enc_;
  ll XX(ll enc){return enc/10000;}
  ll YY(ll enc){return enc%10000;}
  ll valid_enc(ll enc){ return enc/10000<nn and enc%10000<nn; }
}

std::string SendB(int N, int X, int Y) {
  ::nn=N;
  string S(20,'0');
  ll enc=10000ll*X+Y;
  for(ll j=0;j<20;++j)
    S[j]=((enc>>j)&1)+'0';
  yy=Y;
  enc_=enc;
  return S;
}

int Answer(std::string T) {
  int cnt=0;
  for(ll j=0;j<(1<<7);++j){
    ll enc2 = (enc_&((1<<20)-1)) | (j<<20);
    if(enc2 == enc_) return read(T,cnt*14);
    if(valid_enc(enc2))++cnt;
  }
  return -1;
}

Compilation message (stderr)

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while(cnt*14+14>=T.size())T+='0';
      |           ~~~~~~~~~^~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp:13:6: warning: 'll {anonymous}::YY(ll)' defined but not used [-Wunused-function]
   13 |   ll YY(ll enc){return enc%10000;}
      |      ^~
Benjamin.cpp:12:6: warning: 'll {anonymous}::XX(ll)' defined but not used [-Wunused-function]
   12 |   ll XX(ll enc){return enc/10000;}
      |      ^~
Benjamin.cpp:8:8: warning: 'void {anonymous}::write(std::string&, int, ll, int)' defined but not used [-Wunused-function]
    8 |   void write(string&s,int i,ll x,int b=14){ for(ll j=0;j<b;++j) s[i+j]=((x>>j)&1)+'0'; }
      |        ^~~~~

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