| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1062441 | sleepntsheep | Flights (JOI22_flights) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Ali.h"
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
constexpr int BASE=1e9,D=50;
struct bigint{
array<ll,D>v{};
bigint(ll x){ v[0]=x;}
bigint() {}
int cmpr(const bigint &o)const {
for(int i=D-1;i>=0;--i)if(v[i]!=o.v[i])return v[i]<o.v[i]?-1:1;
return 0;
};
const bigint& operator+=(const bigint&o){
ll carry=0;
for(int i=0;i<D;++i){
v[i]=(carry+o.v[i]+v[i]);
carry=v[i]/BASE;
v[i]%=BASE;
}
return *this;
}
const bigint& operator-=(const bigint&o){
for(int i=0;i<D;++i){
v[i]=(v[i]-o.v[i]);
if(v[i]<0)v[i]+=BASE,v[i+1]--;
}
return*this;
}
const bigint& operator*=(ll x){
ll carry=0;
for(int i=0;i<D;++i){
v[i]=(v[i]*x);
carry=v[i]/BASE;
v[i]%=BASE;
}
return *this;
}
friend bigint operator+(bigint&lhs,bigint&rhs){return lhs+=rhs;}
friend bigint operator-(bigint&lhs,bigint&rhs){return lhs-=rhs;}
friend bigint operator*(bigint&lhs,ll rhs){return lhs*=rhs;}
bool operator<(const bigint &o)const{return cmpr(o)==-1;}
bool operator>(const bigint &o)const{return cmpr(o)==1;}
bool operator>=(const bigint &o)const{return cmpr(o)>=0;}
bool operator<=(const bigint &o)const{return cmpr(o)<=0;}
bool operator==(const bigint &o)const{return cmpr(o)==0;}
};
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;}
const int B2=1210;
bigint pw2[3000];
bigint npow[4000];int inited;
string to_string(bigint &b){ string T; for(int i=B2-1;i>=0;--i) if(b<pw2[i]) T+='0'; else T+='1',b-=pw2[i]; return T; }
bigint from_string(string &T){ bigint b; for(int i=0;i<(int)T.size();++i)if(T[i]=='1')b+=pw2[i]; return b; }
void init(){ if(inited)return; inited=1; npow[0]=1; for(int i=1;i<4000;++i) npow[i]=npow[i-1]*10000;
pw2[0]=1;for(int i=1;i<B2;++i)pw2[i]=pw2[i-1]*2; }
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
init();
::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) {
init();
ll enc=read(S,0,20);
vector<int>dis;
for(ll j=0;j<(1<<7);++j){
ll enc2 = (enc&((1<<20)-1)) | (j<<20);
if(valid_enc(enc2))dis.push_back(dist(XX(enc2),YY(enc2)));
}
bigint b;
for(int i=0;i<(int)dis.size();++i)b+=npow[i]*dis[i];
return to_string(b);
}
#include "Benjamin.h"
#include <string>
#include <vector>
using namespace std;
using ll = long long;
constexpr int BASE=1e9,D=50;
struct bigint{
array<ll,D>v{};
bigint(ll x){ v[0]=x;}
bigint() {}
int cmpr(const bigint &o)const {
for(int i=D-1;i>=0;--i)if(v[i]!=o.v[i])return v[i]<o.v[i]?-1:1;
return 0;
};
const bigint& operator+=(const bigint&o){
ll carry=0;
for(int i=0;i<D;++i){
v[i]=(carry+o.v[i]+v[i]);
carry=v[i]/BASE;
v[i]%=BASE;
}
return *this;
}
const bigint& operator-=(const bigint&o){
for(int i=0;i<D;++i){
v[i]=(v[i]-o.v[i]);
if(v[i]<0)v[i]+=BASE,v[i+1]--;
}
return*this;
}
const bigint& operator*=(ll x){
ll carry=0;
for(int i=0;i<D;++i){
v[i]=(v[i]*x);
carry=v[i]/BASE;
v[i]%=BASE;
}
return *this;
}
friend bigint operator+(bigint&lhs,bigint&rhs){return lhs+=rhs;}
friend bigint operator-(bigint&lhs,bigint&rhs){return lhs-=rhs;}
friend bigint operator*(bigint&lhs,ll rhs){return lhs*=rhs;}
bool operator<(const bigint &o)const{return cmpr(o)==-1;}
bool operator>(const bigint &o)const{return cmpr(o)==1;}
bool operator>=(const bigint &o)const{return cmpr(o)>=0;}
bool operator<=(const bigint &o)const{return cmpr(o)<=0;}
bool operator==(const bigint &o)const{return cmpr(o)==0;}
};
namespace {
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; }
const int B2=1346;
bigint pw2[3000];
bigint npow[4000];int inited;
string to_string(bigint &b){ string T; for(int i=B2-1;i>=0;--i) if(b<pw2[i]) T+='0'; else T+='1',b-=pw2[i]; return T; }
bigint from_string(string &T){ bigint b; for(int i=0;i<(int)T.size();++i)if(T[i]=='1')b+=pw2[i]; return b; }
void init(){ if(inited)return; inited=1; npow[0]=1; for(int i=1;i<4000;++i) npow[i]=npow[i-1]*10000;
pw2[0]=1;for(int i=1;i<B2;++i)pw2[i]=pw2[i-1]*2; }
}
std::string SendB(int N, int X, int Y) {
init();
::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) {
init();
bigint b=from_string(T);
vector<int>dis(100);
for(int i=94;i>=0;--i){
int lb=0,ub=10000;
while(ub-lb>1){
int md=lb+(ub-lb)/2;
if(npow[i]*md>b) ub=md;
else lb=md;
}
dis.push_back(ub-1);
b-=npow[i]*(ub-1);
}
reverse(dis.begin(),dis.end());
int cnt=0;
for(ll j=0;j<(1<<7);++j){
ll enc2 = (enc_&((1<<20)-1)) | (j<<20);
if(enc2 == enc_) return dis[cnt];
if(valid_enc(enc2))++cnt;
}
__builtin_unreachable();
}