Submission #567830

#	Time	Username	Problem	Language	Result	Execution time	Memory
567830		tqbfjotld	Flights (JOI22_flights)	C++17	33 / 100	294 ms	2744 KiB

Ali

#include "Ali.h"
#include <bits/stdc++.h>

namespace {

std::vector<int> adjl[10005];
int p[10005][18];
int dep[10005];
void dfs1(int node, int pa){
    p[node][0] = pa;
    for (auto x : adjl[node]){
        if (x==pa) continue;
        dep[x] = dep[node]+1;
        dfs1(x,node);
    }
}
int lca(int a, int b){
    if (dep[a]>dep[b]) std::swap(a,b);
    int t = dep[b]-dep[a];
    for (int x = 0; x<18; x++){
        if (t&(1<<x)) b = p[b][x];
    }
    if (a==b) return a;
    for (int x = 17; x>=0; x--){
        if (p[a][x]!=p[b][x]){
            a = p[a][x];
            b = p[b][x];
        }
    }
    return p[a][0];
}
int n;
int getdist(int a, int b){
    if (a>=n || b>=n) return 0;
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}

}

void Init(int N, std::vector<int> U, std::vector<int> V) {
    for (int x = 0; x<N; x++){
        adjl[x].clear();
    }
    for (int x = 0; x<N-1; x++){
        adjl[U[x]].push_back(V[x]);
        adjl[V[x]].push_back(U[x]);
    }
    dfs1(0,-1);
    n = N;
    for (int x = 0; x<N; x++){
        SetID(x,2*x+(dep[x]&1));
    }
    for (int x = 1; x<18; x++){
        for (int y = 0; y<N; y++){
            if (p[y][x-1]==-1) p[y][x] = -1;
            else p[y][x] = p[p[y][x-1]][x-1];
        }
    }
}

std::string SendA(std::string S) {
    int thing = 0;
    for (int x = 0; x<20; x++){
        if (S[x]=='1') thing += 1<<x;
    }
    std::string ans;
    for (int x = thing; x<n*(n-1)/2; x+=(1<<20)){
        int l = 0;
        int r = n-1;
        while (l+1<r){
            int mid = (l+r)/2;
            if (x<(mid)*(mid+1)/2){
                r = mid;
            }
            else l = mid;
        }
        int b = r;
        int a = x-(b)*(b-1)/2;
        int t = getdist(a,b);
        //printf("push val %d %d\n",a,b);
        for (int x = 1; x<=13; x++){
            ans.push_back((t&(1<<x))?'1':'0');
        }
    }
    return ans;
}

Benjamin

#include "Benjamin.h"
#include <bits/stdc++.h>

namespace {

int storeX,storeY;
int storenum;

}

std::string SendB(int N, int X, int Y) {
    int n1 = X/2;
    int n2 = Y/2;
    storeX = X;
    storeY = Y;
    std::string ans;
    if (n1>n2){
        std::swap(n1,n2);
        std::swap(X,Y);
        std::swap(storeX,storeY);
    }
    int num = 0;
    for (int x = 0; x<n2; x++){
        num += x;
    }
    num += n1;
    for (int x = 0; x<20; x++){
        ans.push_back((num&(1<<x))?'1':'0');
    }
    storenum = num;
    return ans;
}

int Answer(std::string T) {
    if (storeX==storeY) return 0;
    int t = storenum>>20;
    int ans = 0;
    for (int x = 0; x<13; x++){
        if (T[t*13+x]=='1'){
            ans += (1<<x);
        }
    }
    ans<<=1;
    if ((storeX&1)!=(storeY&1)){
        ans++;
    }
    return ans;
}

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: 18 / 85