GitHub 源文件 Markdown 中文

Encrypted Packets and Network Resets

Indicative time limit: 1.5 seconds. Memory limit: 512 MiB. Recalibrate as twice the slowest standard median in the target environment, rounded up to 0.5 seconds. See the environment.

Story

A relay station adds a link whenever it receives an encrypted packet. If a route becomes short enough, it clears all links and starts another round. Reproduce the effect of every packet.

(This story was rewritten by GPT-6.)

Formal Problem Statement

Maintain a weighted directed multigraph with \(n\) vertices. Parallel edges are allowed; self-loops are forbidden. A logical edge is a tuple \((u,v,x,y)\) . If \(y=0\) , it provides an arc from \(u\) to \(v\) of weight \(x\) . If \(y=1\) , it permits travel in both directions with weight \(x\) in either direction. A bidirectional logical edge still counts as one edge.

First add \(m\) unencrypted initial logical edges. This does not trigger a reset, even if the shortest distance from vertex 1 to vertex \(n\) is already at most the threshold \(T\) .

Then process \(k\) encrypted packets in order. Decrypt each of the four fields of packet \(c\) by

\[ a=a'\mathbin{\mathrm{XOR}}\left(((b+3)(c+37))\bmod998244353\right) \]

Here \(a'\) is the input field, \(a\) is its decoded value, \(c\) is numbered from one, and \(b\) is the total number of logical edges deleted by all previous resets, initially zero. Use the same key for all four fields to obtain \((u,v,x,y)\) , then add that edge.

If the shortest distance from vertex 1 to vertex \(n\) is now at most \(T\) , delete every current logical edge, including the new one, increase \(b\) by that count, and output 1. Otherwise retain the graph and output 0. An unreachable destination has infinite distance. Initial edges count toward \(b\) when a reset deletes them.

The first packet in Sample 1 adds a weight-2 link and completes a route of length \(3+2=5\) . Since the threshold is 5, the network resets.

Input Format

The first line contains n m k T . The next \(m\) lines contain unencrypted u v x y . The following \(k\) lines contain four encrypted fields per packet, in packet order.

Output Format

Print one line of \(k\) space-separated zeros or ones, indicating whether each packet triggers a reset.

Sample 1

Input

4 1 5 5
1 2 3 0
112 118 112 114
194 199 197 194
201 203 200 200
206 201 200 205
337 340 336 337

Output

1 0 0 1 1

Sample 2

Input

2 1 2 0
1 2 0 0
112 115 10082 114
194 193 195 194

Output

1 1

Constraints and Scoring

\(2\le n\le10^5\) , \(1\le m\le10^5\) , \(1\le k\le50000\) , and \(0\le T\le100\) . Initial and decoded edges satisfy \(1\le u,v\le n\) , \(u\ne v\) , \(0\le x\le10000\) , and \(y\in\{0,1\}\) . Encrypted fields belong to \([0,2^{30}-1]\) , and their decoded values are guaranteed legal.

Completed by Codex (GPT-6) and recorded as a redesign: the first line includes \(T\) , with \(0\le T\le100\) , and logical-edge counting explicitly covers bidirectional and initial edges.

Score	Additional constraints
100%	None

There are ten formal files worth 10% each.

See the test recipes.