| 比赛 |
期末考试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;
}