제출 #1143392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143392		CDuong	Flights (JOI22_flights)	C++17	15 / 100	34 ms	4592 KiB

Ali

#include "Ali.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

namespace {

int N;
vector<int> dep, ap;
vector<vector<int>> g;
vector<vector<pair<int, int>>> st;

void init_lca() {
  st.assign(1, {});
  ap.assign(N, 0);
  dep.assign(N, 0);
}

void dfs(int u, int p) {
  ap[u] = isz(st[0]);
  st[0].emplace_back(dep[u], u);
  for (auto v : g[u]) if (v != p) {
    dep[v] = dep[u] + 1;
    dfs(v, u);
    st[0].emplace_back(dep[u], u);
  }
}

void build_sparse() {
  for (int p = 1, i = 1; p << 1 <= isz(st[0]); p <<= 1, ++i) {
    st.emplace_back(isz(st[0]) - (p << 1) + 1);
    for (int j = 0; j < isz(st[i]); ++j) {
      st[i][j] = min(st[i - 1][j], st[i - 1][j + p]);
    }
  }
}

int LCA(int u, int v) {
  int l = ap[u], r = ap[v];
  if (l > r) swap(l, r);
  ++r;
  assert(0 <= l and l <= r and r <= isz(st[0]));
  int d = __lg(r - l);
  return min(st[d][l], st[d][r - (1 << d)]).second;
}

int dist(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

}

void Init(int N, vector<int> U, vector<int> V) {
  ::N = N;
  g.assign(N, {});
  for (int i = 0; i < N - 1; ++i) {
    int u = U[i], v = V[i];
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  for (int i = 0; i < N; ++i) {
    SetID(i, i);
  }
  init_lca();
  dfs(0, -1);
  build_sparse();
}

string SendA(string S) {
  int X = 0, Y = 0;
  for (int i = 0; i < 14; ++i) X |= (S[i] - '0') << i;
  for (int i = 0; i <  6; ++i) Y |= (S[i + 14] - '0') << i;
  string res = "";
  for (int i = Y; i < N; i += 1 << 6) {
    int d = dist(X, i);
    for (int j = 0; j < 14; ++j) res.push_back((d >> j & 1) + '0');
  }
  return res;
}

Benjamin

#include "Benjamin.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

namespace {

int Y;

}

string SendB(int N, int X, int Y) {
  ::Y = Y >> 6;
  string res = "";
  for (int i = 0; i < 14; ++i) res.push_back((X >> i & 1) + '0');
  for (int i = 0; i <  6; ++i) res.push_back((Y >> i & 1) + '0');
  return res;
}

int Answer(string T) {
  int st = 14 * Y, res = 0;
  for (int i = 0; i < 14; ++i) res |= (T[st + i] - '0') << i;
  return res;
}

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