比赛 期末考试1 评测结果 WAAAATTTAT
题目名称 Communication 最终得分 50
用户昵称 LikableP 运行时间 4.546 s
代码语言 C++ 内存使用 14.92 MiB
提交时间 2026-02-08 11:34:35
显示代码纯文本
#include <cstdio>
#include <cctype>

namespace IO {
  const int BUFSIZE = 1 << 20;
  
  char buf[BUFSIZE], *p1, *p2;
  
  char gc() {
    if (p1 == p2) {
      p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin);
      if (p1 == p2) return EOF;
    }
    return *p1++;
  }
  
  template <typename T> T read() {
    T res = 0, f = 1;
    char ch = gc();
    for (; !isdigit(ch); ch = gc()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = gc()) res = (res << 3) + (res << 1) + (ch ^ 48);
    return res * f;
  }
  
  template <typename T> void write(T x, char ed = '\n') {
    if (x < 0) x = -x, putchar('-');
    static int sta[sizeof(T) << 2], top = 0;
    do {
      sta[++top] = x % 10;
      x /= 10;
    } while (x);
    while (top) {
      putchar(sta[top--] ^ 48);
    }
    putchar(ed);
  }
};

#include <algorithm>
#include <queue>
#include <cstring>
typedef long long ll;
const int MAXN = 5e5 + 10;

int n;
ll L, R;
ll a[MAXN], b[MAXN], w[MAXN];

namespace Sub1 {
  bool Legal(int u, int v) {
    return L <= a[u] + b[v] && a[u] + b[v] <= R;
  }

  int choose[MAXN];
  ll res = 0x7fffffffffffffff;

  void dfs(int step, int ed, ll ans) {
    if (choose[step - 1] == ed) return ;
    if (ans > res) return ;
    for (int i = choose[step - 1] + 1; i <= ed - 1; ++i) if (Legal(choose[step - 1], i)) {
      choose[step] = i;
      dfs(step + 1, ed, ans + w[i]);
    }
    if (Legal(choose[step - 1], ed)) {
      res = std::min(res, ans + w[ed]);
    }
  }

  int Work() {
    choose[1] = 1;
    IO::write(w[1], ' ');
    for (int i = 2; i <= n; ++i) {
      res = 0x7fffffffffffffff;
      dfs(2, i, w[1]);
      IO::write(res == 0x7fffffffffffffff ? -1 : res, " \n"[i == n]);
    }
    return 0;
  }
};

namespace Sub3 {
  bool Legal(int u, int v) {
    return L <= a[u] + b[v] && a[u] + b[v] <= R;
  }

  std::priority_queue<std::pair<ll, int>> pq;
  ll dis[MAXN];
  bool vis[MAXN];

  void Dijkstra(int st) {
    memset(dis, 0x3f, sizeof dis);
    dis[st] = w[st];
    pq.push({-dis[st], st});
    while (!pq.empty()) {
      int u = pq.top().second; pq.pop();
      if (vis[u]) continue;
      vis[u] = true;
      for (int v = u + 1; v <= n; ++v) if (Legal(u, v)) {
        if (dis[v] > dis[u] + w[v]) {
          dis[v] = dis[u] + w[v];
          pq.push({-dis[v], v});
        }
      }
    }
  }

  int Work() {
    Dijkstra(1);
    for (int i = 1; i <= n; ++i) {
      IO::write(dis[i] == 0x3f3f3f3f3f3f3f3f ? -1 : dis[i], " \n"[i == n]);
    }
    return 0;
  }
};

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("tioj_communication.in", "r", stdin);
    freopen("tioj_communication.out", "w", stdout);
  #endif

  n = IO::read<int>(), L = IO::read<ll>(), R = IO::read<ll>();
  for (int i = 1; i <= n; ++i) a[i] = IO::read<ll>();
  for (int i = 1; i <= n; ++i) b[i] = IO::read<ll>();
  for (int i = 1; i <= n; ++i) w[i] = IO::read<ll>();

  Sub3::Work();
  return 0;
}