Submission #787488

#	Time	Username	Problem	Language	Result	Execution time	Memory
787488		eltu0815	Flights (JOI22_flights)	C++17	15 / 100	366 ms	540672 KiB

Ali

#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int n;
    int dep[10005], parent[10005][14];
    vector<int> tree[10005];
}

int LCA(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v], j = 0;
    while(diff) {
        if(diff & 1) u = parent[u][j];
        diff >>= 1; ++j;
    }
    if(u == v) return u;
    for(int i = 13; i >= 0; --i) {
        if(parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}

void dfs(int node, int par) {
    dep[node] = dep[par] + 1; parent[node][0] = par;
    for(auto v : tree[node]) {
        if(v == par) continue;
        dfs(v, node);
    }
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    for(int i = 0; i < n - 1; ++i) {
        tree[U[i]].push_back(V[i]);
        tree[V[i]].push_back(U[i]);
    }
    dfs(0, 0);
    for(int j = 1; j <= 13; ++j) for(int i = 0; i < n; ++i) parent[i][j] = parent[parent[i][j - 1]][j - 1];
    for(int i = 0; i < n; ++i) SetID(i, i);
}

std::string SendA(std::string S) {
    int x = 0, y = 0;
    for(int i = 0; i <= 13; ++i) x |= (S[i] - '0') << i;
    for(int i = 14; i < 20; ++i) y |= (S[i] - '0') << (i - 14);
    
    string ret;
    for(int i = 0; i < (1 << 8); ++i) {
        int ny = ((i << 6) | y);
        if(ny >= n) continue;
        int dist = dep[x] + dep[ny] - 2 * dep[LCA(x, ny)];
        for(int j = 0, t = 1; j <= 13; ++j, t <<= 1) {
            if(dist & t) ret.push_back('1');
            else ret.push_back('0');
        }
    }
    return ret;
}

Benjamin

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

namespace {
    int n;
    int x, y;
    int y6;
}

std::string SendB(int N, int X, int Y) {
    n = N; x = X; y = Y;
    string ret;
    for(int i = 0, t = 1; i <= 13; ++i, t <<= 1) {
        if(X & t) ret += '1';
        else ret += '0';
    }
    for(int i = 0, t = 1; i <= 5; ++i, t <<= 1) {
        if(Y & t) ret += '1';
        else ret += '0';
    }
    y6 = y & ((1 << 6) - 1);
    return ret;
}

int Answer(std::string T) {
    int idx = 0;
    for(int i = 0; i < (1 << 8); ++i) {
        int ny = ((i << 6) | y6);
        if(ny >= n) continue;
        if(ny != y) idx += 14;
        else {
            int ret = 0;
            for(int j = 0; j <= 13; ++j) ret |= (T[idx + j] - '0') << j;
            return ret;
        }
    }
    return 0;
}

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