oj.uz

Submission #787749

# Submission time Handle Problem Language Result Execution time Memory
787749 2023-07-19T12:03:43 Z eltu0815 Flights (JOI22_flights) C++17
15 / 100
 35 ms 2352 KB 
#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; ++i) tree[i].clear();
    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;
}

#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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 656 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 0 ms 656 KB Output is correct
5 Correct 0 ms 656 KB Output is correct
6 Correct 4 ms 1744 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 4 ms 1880 KB Output is correct
9 Correct 4 ms 1900 KB Output is correct
10 Correct 6 ms 1928 KB Output is correct
11 Correct 5 ms 1552 KB Output is correct
12 Correct 4 ms 1876 KB Output is correct
13 Correct 5 ms 1804 KB Output is correct
14 Correct 4 ms 1880 KB Output is correct
15 Correct 4 ms 2192 KB Output is correct
16 Correct 4 ms 1884 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 656 KB Output is correct
2 Partially correct 35 ms 2352 KB Output is partially correct
3 Halted 0 ms 0 KB -