Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Think of as time. Edge is usable sometime in the interval ; if you arrive before , you just wait until then.
For one fixed walk, if it works for some , then raising up to the minimum capacity on that walk still works. So an optimal is always equal to some edge capacity .
At a fixed time , all edges with can be crossed without changing time. They form ordinary connected components, and inside one such component all vertices share the same future reachable vertex values.
Process times from large to small. Maintain : the largest vertex value reachable from if the current time is already at least the time being processed. Starting earlier can wait, so later information flows backward.
Use divide and conquer over the compressed event times. In a segment, contract every edge active for the whole segment, recurse on the right half first, copy back only reachable values, then recurse on the left half. Queries live at edge capacities and force the at-least-one-edge condition.
Think of the state as time.
An edge is available during the closed interval . If you are at time , traversing it just means waiting until and then crossing. If , you are too late. So the problem is a temporal graph with waiting allowed.
The first key simplification is that we only need to try edge capacities. Take any feasible walk using edges , and let
If the walk is feasible for some , then every prefix maximum of lows is already at most every later capacity where it needs to be. Raising up to still keeps for every edge. Therefore the same walk is feasible with , and the score only improves. So the optimal starting value is always some edge capacity. Brute forcing every integer would be pure CPU donation.
Now fix a candidate time . Edges satisfying
can be crossed immediately without increasing time. Thus they form normal undirected connected components. If a component contains an edge whose capacity is exactly , then starting from any vertex in this component we can traverse at least one edge at time . After that, we only care about the maximum vertex value reachable from this component at time or later.
So define as the maximum reachable from the current contracted node , allowing zero more edges. The answer update at time is
for every vertex in an active component that is certified by some edge with capacity . The zero-more-edges allowance in is fine because the query edge already guarantees that at least one edge has been traversed.
We compress all endpoints. For equal numeric values, put low endpoints before capacity endpoints, so an edge with still has a nonempty active interval. Each edge becomes an interval on this compressed axis, and it creates one query at .
The remaining job is dynamic connectivity over intervals, plus backward DP. Use a divide-and-conquer recursion on a time segment :
At a leaf time , contract the active edges at that exact time, merge inside each component, and answer every query there with .
Correctness follows from three facts. First, the interval interpretation exactly matches the update rule . Second, every optimal walk can be shifted up to the minimum capacity on that walk, so checking only capacity queries loses nothing. Third, the recursion preserves temporal order: all information from later times is converted into reachable vertex values before earlier times are processed. Since edges covering a whole segment are active at every time in that segment, contracting them cannot change reachability.
If , no query ever exists, so every answer is . Multiple edges are harmless, and returning to the same vertex is handled automatically because an active component certified by an edge lets you spend at least one traversal.
The total number of interval pieces over the recursion is , and each level performs linear work in its current edges, queries, and contracted nodes. The complexity is
per total input size, with memory within the same order for the recursion buffers.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Solver {
struct Edge {
int u, v, l, r;
};
struct Query {
int t, u;
};
struct Event {
int idx;
ll value;
};
struct Adj {
int to, next;
};
int n = 0, m = 0, total = 0, edgeCnt = 0;
vector<ll> coord, best, answer;
vector<int> head, comp, remap;
vector<Adj> adj;
vector<Query> queries;
vector<vector<Edge>> leftPart, rightPart;
vector<int> stackNodes;
void ensureNode(int id) {
if (id < (int)best.size()) return;
int old = (int)best.size();
int now = max(id + 1, old * 2 + 1);
best.resize(now, 0);
answer.resize(now, -1);
head.resize(now, 0);
comp.resize(now, 0);
remap.resize(now, 0);
}
int newNode() {
++total;
ensureNode(total);
best[total] = 0;
answer[total] = -1;
head[total] = comp[total] = remap[total] = 0;
return total;
}
void addGraphEdge(int u, int v) {
if (edgeCnt + 2 >= (int)adj.size()) adj.resize(adj.size() * 2 + 10);
adj[++edgeCnt] = {v, head[u]};
head[u] = edgeCnt;
adj[++edgeCnt] = {u, head[v]};
head[v] = edgeCnt;
}
void markComponent(int root) {
comp[root] = root;
stackNodes.clear();
stackNodes.push_back(root);
while (!stackNodes.empty()) {
int u = stackNodes.back();
stackNodes.pop_back();
for (int e = head[u]; e; e = adj[e].next) {
int v = adj[e].to;
if (!comp[v]) {
comp[v] = root;
stackNodes.push_back(v);
}
}
}
}
void solveRange(int depth, int l, int r, vector<Edge>& edges, int qcnt, int vl, int vr) {
if (edges.empty()) {
for (int i = 1; i <= qcnt; ++i) {
int u = queries[i].u;
answer[u] = max(answer[u], best[u] + coord[queries[i].t]);
}
return;
}
int mid = (l + r) >> 1;
leftPart[depth].clear();
rightPart[depth].clear();
for (int i = vl; i <= vr; ++i) {
head[i] = comp[i] = remap[i] = 0;
}
edgeCnt = 0;
for (const Edge& e : edges) {
if (e.l <= l && r <= e.r) {
addGraphEdge(e.u, e.v);
} else {
if (e.l <= mid) leftPart[depth].push_back(e);
if (e.r > mid) rightPart[depth].push_back(e);
}
}
for (int i = vl; i <= vr; ++i) {
if (!comp[i]) markComponent(i);
}
if (l == r) {
for (int i = vl; i <= vr; ++i) {
best[comp[i]] = max(best[comp[i]], best[i]);
}
for (int i = 1; i <= qcnt; ++i) {
int u = comp[queries[i].u];
answer[u] = max(answer[u], best[u] + coord[l]);
}
for (int i = vl; i <= vr; ++i) {
best[i] = max(best[i], best[comp[i]]);
answer[i] = max(answer[i], answer[comp[i]]);
}
return;
}
int saved = total;
for (Edge& e : rightPart[depth]) {
int a = comp[e.u], b = comp[e.v];
if (!remap[a]) remap[a] = newNode();
if (!remap[b]) remap[b] = newNode();
e.u = remap[a];
e.v = remap[b];
}
int rightCnt = 0;
for (int i = 1; i <= qcnt; ++i) {
if (queries[i].t > mid) {
int a = comp[queries[i].u];
if (!remap[a]) remap[a] = newNode();
queries[i].u = remap[a];
swap(queries[i], queries[++rightCnt]);
}
}
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) best[u] = max(best[u], best[i]);
}
if (saved < total) {
solveRange(depth + 1, mid + 1, r, rightPart[depth], rightCnt, saved + 1, total);
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) {
best[i] = max(best[i], best[u]);
answer[i] = max(answer[i], answer[u]);
}
}
}
total = saved;
for (int i = vl; i <= vr; ++i) remap[i] = 0;
for (Edge& e : leftPart[depth]) {
int a = comp[e.u], b = comp[e.v];
if (!remap[a]) remap[a] = newNode();
if (!remap[b]) remap[b] = newNode();
e.u = remap[a];
e.v = remap[b];
}
int leftCnt = 0;
for (int i = rightCnt + 1; i <= qcnt; ++i) {
int a = comp[queries[i].u];
if (!remap[a]) remap[a] = newNode();
queries[i].u = remap[a];
swap(queries[i], queries[++leftCnt]);
}
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) best[u] = max(best[u], best[i]);
}
if (saved < total) {
solveRange(depth + 1, l, mid, leftPart[depth], leftCnt, saved + 1, total);
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) {
best[i] = max(best[i], best[u]);
answer[i] = max(answer[i], answer[u]);
}
}
}
total = saved;
}
void run() {
cin >> n >> m;
vector<ll> val(n + 1);
for (int i = 1; i <= n; ++i) cin >> val[i];
if (m == 0) {
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
cout << -1;
}
cout << '\n';
return;
}
vector<int> eu(m + 1), ev(m + 1), lowPos(m + 1), highPos(m + 1);
vector<Event> events;
events.reserve(2 * m);
for (int i = 1; i <= m; ++i) {
ll w, low;
cin >> eu[i] >> ev[i] >> w >> low;
events.push_back({i, w});
events.push_back({i + m, low});
}
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
if (a.value != b.value) return a.value < b.value;
return a.idx > b.idx;
});
coord.assign(2 * m + 1, 0);
for (int i = 1; i <= 2 * m; ++i) {
coord[i] = events[i - 1].value;
if (events[i - 1].idx > m) lowPos[events[i - 1].idx - m] = i;
else highPos[events[i - 1].idx] = i;
}
int initialNodes = n + 4 * m + 10;
best.assign(initialNodes, 0);
answer.assign(initialNodes, -1);
head.assign(initialNodes, 0);
comp.assign(initialNodes, 0);
remap.assign(initialNodes, 0);
adj.assign(2 * m + 5, {0, 0});
queries.assign(m + 1, {0, 0});
leftPart.assign(32, vector<Edge>());
rightPart.assign(32, vector<Edge>());
stackNodes.reserve(n + 2 * m + 5);
for (int i = 1; i <= n; ++i) best[i] = val[i];
vector<Edge> allEdges;
allEdges.reserve(m);
for (int i = 1; i <= m; ++i) {
allEdges.push_back({eu[i], ev[i], lowPos[i], highPos[i]});
queries[i] = {highPos[i], eu[i]};
}
total = n;
solveRange(0, 1, 2 * m, allEdges, m, 1, n);
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
cout << answer[i];
}
cout << '\n';
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Solver {
struct Edge {
int u, v, l, r;
};
struct Query {
int t, u;
};
struct Event {
int idx;
ll value;
};
struct Adj {
int to, next;
};
int n = 0, m = 0, total = 0, edgeCnt = 0;
vector<ll> coord, best, answer;
vector<int> head, comp, remap;
vector<Adj> adj;
vector<Query> queries;
vector<vector<Edge>> leftPart, rightPart;
vector<int> stackNodes;
void ensureNode(int id) {
if (id < (int)best.size()) return;
int old = (int)best.size();
int now = max(id + 1, old * 2 + 1);
best.resize(now, 0);
answer.resize(now, -1);
head.resize(now, 0);
comp.resize(now, 0);
remap.resize(now, 0);
}
int newNode() {
++total;
ensureNode(total);
best[total] = 0;
answer[total] = -1;
head[total] = comp[total] = remap[total] = 0;
return total;
}
void addGraphEdge(int u, int v) {
if (edgeCnt + 2 >= (int)adj.size()) adj.resize(adj.size() * 2 + 10);
adj[++edgeCnt] = {v, head[u]};
head[u] = edgeCnt;
adj[++edgeCnt] = {u, head[v]};
head[v] = edgeCnt;
}
void markComponent(int root) {
comp[root] = root;
stackNodes.clear();
stackNodes.push_back(root);
while (!stackNodes.empty()) {
int u = stackNodes.back();
stackNodes.pop_back();
for (int e = head[u]; e; e = adj[e].next) {
int v = adj[e].to;
if (!comp[v]) {
comp[v] = root;
stackNodes.push_back(v);
}
}
}
}
void solveRange(int depth, int l, int r, vector<Edge>& edges, int qcnt, int vl, int vr) {
if (edges.empty()) {
for (int i = 1; i <= qcnt; ++i) {
int u = queries[i].u;
answer[u] = max(answer[u], best[u] + coord[queries[i].t]);
}
return;
}
int mid = (l + r) >> 1;
leftPart[depth].clear();
rightPart[depth].clear();
for (int i = vl; i <= vr; ++i) {
head[i] = comp[i] = remap[i] = 0;
}
edgeCnt = 0;
for (const Edge& e : edges) {
if (e.l <= l && r <= e.r) {
addGraphEdge(e.u, e.v);
} else {
if (e.l <= mid) leftPart[depth].push_back(e);
if (e.r > mid) rightPart[depth].push_back(e);
}
}
for (int i = vl; i <= vr; ++i) {
if (!comp[i]) markComponent(i);
}
if (l == r) {
for (int i = vl; i <= vr; ++i) {
best[comp[i]] = max(best[comp[i]], best[i]);
}
for (int i = 1; i <= qcnt; ++i) {
int u = comp[queries[i].u];
answer[u] = max(answer[u], best[u] + coord[l]);
}
for (int i = vl; i <= vr; ++i) {
best[i] = max(best[i], best[comp[i]]);
answer[i] = max(answer[i], answer[comp[i]]);
}
return;
}
int saved = total;
for (Edge& e : rightPart[depth]) {
int a = comp[e.u], b = comp[e.v];
if (!remap[a]) remap[a] = newNode();
if (!remap[b]) remap[b] = newNode();
e.u = remap[a];
e.v = remap[b];
}
int rightCnt = 0;
for (int i = 1; i <= qcnt; ++i) {
if (queries[i].t > mid) {
int a = comp[queries[i].u];
if (!remap[a]) remap[a] = newNode();
queries[i].u = remap[a];
swap(queries[i], queries[++rightCnt]);
}
}
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) best[u] = max(best[u], best[i]);
}
if (saved < total) {
solveRange(depth + 1, mid + 1, r, rightPart[depth], rightCnt, saved + 1, total);
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) {
best[i] = max(best[i], best[u]);
answer[i] = max(answer[i], answer[u]);
}
}
}
total = saved;
for (int i = vl; i <= vr; ++i) remap[i] = 0;
for (Edge& e : leftPart[depth]) {
int a = comp[e.u], b = comp[e.v];
if (!remap[a]) remap[a] = newNode();
if (!remap[b]) remap[b] = newNode();
e.u = remap[a];
e.v = remap[b];
}
int leftCnt = 0;
for (int i = rightCnt + 1; i <= qcnt; ++i) {
int a = comp[queries[i].u];
if (!remap[a]) remap[a] = newNode();
queries[i].u = remap[a];
swap(queries[i], queries[++leftCnt]);
}
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) best[u] = max(best[u], best[i]);
}
if (saved < total) {
solveRange(depth + 1, l, mid, leftPart[depth], leftCnt, saved + 1, total);
for (int i = vl; i <= vr; ++i) {
int u = remap[comp[i]];
if (u) {
best[i] = max(best[i], best[u]);
answer[i] = max(answer[i], answer[u]);
}
}
}
total = saved;
}
void run() {
cin >> n >> m;
vector<ll> val(n + 1);
for (int i = 1; i <= n; ++i) cin >> val[i];
if (m == 0) {
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
cout << -1;
}
cout << '\n';
return;
}
vector<int> eu(m + 1), ev(m + 1), lowPos(m + 1), highPos(m + 1);
vector<Event> events;
events.reserve(2 * m);
for (int i = 1; i <= m; ++i) {
ll w, low;
cin >> eu[i] >> ev[i] >> w >> low;
events.push_back({i, w});
events.push_back({i + m, low});
}
sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
if (a.value != b.value) return a.value < b.value;
return a.idx > b.idx;
});
coord.assign(2 * m + 1, 0);
for (int i = 1; i <= 2 * m; ++i) {
coord[i] = events[i - 1].value;
if (events[i - 1].idx > m) lowPos[events[i - 1].idx - m] = i;
else highPos[events[i - 1].idx] = i;
}
int initialNodes = n + 4 * m + 10;
best.assign(initialNodes, 0);
answer.assign(initialNodes, -1);
head.assign(initialNodes, 0);
comp.assign(initialNodes, 0);
remap.assign(initialNodes, 0);
adj.assign(2 * m + 5, {0, 0});
queries.assign(m + 1, {0, 0});
leftPart.assign(32, vector<Edge>());
rightPart.assign(32, vector<Edge>());
stackNodes.reserve(n + 2 * m + 5);
for (int i = 1; i <= n; ++i) best[i] = val[i];
vector<Edge> allEdges;
allEdges.reserve(m);
for (int i = 1; i <= m; ++i) {
allEdges.push_back({eu[i], ev[i], lowPos[i], highPos[i]});
queries[i] = {highPos[i], eu[i]};
}
total = n;
solveRange(0, 1, 2 * m, allEdges, m, 1, n);
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
cout << answer[i];
}
cout << '\n';
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
}