Mooclear Reactor
실버 II의견: 0
Bessie is designing a nuclear reactor to power Farmer John's lucrative new AI
data center business, CowWeave!
The reactor core consists of \(N\) (\(1\le N \le 2\cdot 10^5\)) fuel rods, numbered
\(1\) through \(N\). The \(i\)-th rod has a "stable operating range" \([l_i, r_i]\)
(\(-10^9 \leq l_i \leq r_i \leq 10^9\)), meaning it can only generate power if its
energy \(a_i\) (chosen by Bessie) satisfies \(l_i \le a_i \le r_i\); otherwise, it
sits idle and does not generate power. Moreover, \(a_i\) must always be an
integer. Note that \(a_i\) can be any integer, not limited to
\([-10^9, 10^9]\).
However, quantum interactions between the rods mean that there are \(M\)
constraints of the form \((x, y, z)\) where Bessie must satisfy \(a_x + a_y = z\)
(\(1 \leq x,y \leq N\) and \(-10^9\le z\le 10^9\)) to prevent the reactor from
melting down.
Help Bessie find the maximum number of power-generating rods she can achieve in
her design without it melting down!
Problem credits: Akshaj Arora
SCORING
- Input 4: \(x = y\) for all constraints.
- Inputs 5-7: \(|x-y|=1\) for all constraints.
- Inputs 8-10: \(|x-y|\le 1\) for all constraints.
- Inputs 11-13: No additional conditions.
Problem credits: Akshaj Arora
The first line contains \(T\) (\(1\le T\le 10\)), the number of independent tests.
Each test is specified in the following format:
- The first line contains the two integers \(N\) and \(M\).
- The second line contains the \(N\) integers \(l_1, \dots, l_N\).
- The third line contains the \(N\) integers \(r_1, \dots, r_N\).
- The next \(M\) lines each contain three integers \(x\), \(y\), and \(z\), each representing a constraint.
It is guaranteed that neither the sum of \(N\) nor the sum of \(M\) over all tests
exceeds \(4\cdot 10^5\).
If no choice of rod energies exists that satisfies all constraints, output \(-1\).
Otherwise, output the maximum number of power-generating rods Bessie can
achieve.
2
3 3
1 2 3
1 2 3
1 1 2
2 2 10
1 1 4
3 2
1 2 3
1 2 3
1 1 2
2 2 10-1
2In the second test, the constraints require that:
- \(a_1 + a_1 = 2\)
- \(a_2 + a_2 = 10\)
Choosing energies \(a=[1, 5, 3]\) results in \(2\) power-generating rods because:
- \(l_1 = 1 \leq a_1 \leq 1 = r_1\)
- \(l_3 = 3 \leq a_3 \leq 3 = r_3\)
and \(a\) satisfies all required constraints.
1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 03Choosing rod energies \(a=[10, -10, 10]\) results in \(3\) power-generating rods.
5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 22
-1
1
-1
1riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver
평가 및 의견
Mooclear Reactor
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mooclear Reactor