結果
| 問題 | No.1451 集団登校 |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:37 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 291 ms / 2,000 ms |
| コード長 | 7,096 bytes |
| コンパイル時間 | 186 ms |
| コンパイル使用メモリ | 82,636 KB |
| 実行使用メモリ | 93,484 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:58 |
| 合計ジャッジ時間 | 5,711 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
import sys
# Setting a higher recursion depth limit might be necessary for deep DSU paths
# in worst-case scenarios, although iterative find is used which avoids stack depth issues for find().
# Setting it defensively. 2*10^5 + 10 is a safe upper bound N + M + buffer.
try:
# Increase the recursion depth limit for potentially deep call stacks
# (though unlikely with iterative find).
sys.setrecursionlimit(200010)
except (ValueError, OverflowError):
# If the system restricts setting a high limit (e.g., OS limits),
# proceed with the default limit. The iterative find function helps mitigate this risk.
pass
# Define the modulus for calculations
MOD = 10**9 + 7
# Function for fast modular exponentiation (base^power % MOD)
# Used for calculating modular inverse efficiently.
def fast_pow(base, power):
"""
Computes (base^power) % MOD using binary exponentiation.
"""
result = 1
while power > 0:
# If power is odd, multiply result with base
if power % 2 == 1:
result = (result * base) % MOD
# Square the base and halve the power
base = (base * base) % MOD
power //= 2
return result
# Function to calculate modular multiplicative inverse using Fermat's Little Theorem
# Calculates a^(MOD-2) % MOD, which is the inverse of a modulo MOD (if MOD is prime).
def inverse(a):
"""
Computes the modular multiplicative inverse of a modulo MOD.
Assumes MOD is a prime number and a is not divisible by MOD.
"""
return fast_pow(a, MOD - 2)
# Precompute the modular inverse of 2, as it's needed frequently when merging equal-sized groups.
inv2 = inverse(2)
# Global variables for Disjoint Set Union (DSU) state. Using globals simplifies function calls.
parent = [] # parent[i] stores the parent of node i
size = [] # size[i] stores the size of the set rooted at i (only valid for roots)
prob = [] # prob[i] stores the probability that student i is the leader of their current group
members = [] # members[i] is a list storing student IDs in the group rooted at i (only valid for roots)
# Iterative Find operation with Path Compression
# Finds the representative (root) of the set containing element i and compresses the path.
def find(i):
"""
Finds the root of the set containing element i using iterative path compression.
Returns the root of the set.
"""
global parent # Indicate usage of global parent list
root = i
path = [] # Stores nodes encountered on the path to the root
# Traverse up the tree to find the root
while parent[root] != root:
path.append(root)
root = parent[root]
# Apply path compression: make all nodes on the path point directly to the root
# This optimizes future find operations for these nodes.
for node in path:
parent[node] = root
return root
# Union operation logic: merges the sets containing elements a and b
def unite(a, b):
"""
Merges the groups containing students a and b according to the problem rules.
Updates probabilities based on group sizes. Uses union-by-size heuristic.
"""
global parent, size, prob, members, inv2, MOD # Indicate modification of global state variables
# Find the roots of the sets containing a and b
Ra = find(a)
Rb = find(b)
# If a and b are already in the same set, no action is needed
if Ra == Rb:
return
# Union by size heuristic: Always merge the smaller set into the larger set.
# This keeps the DSU trees relatively balanced and ensures efficient operations.
if size[Ra] > size[Rb]:
# Swap Ra and Rb so that Ra always represents the root of the smaller (or equal size) set
Ra, Rb = Rb, Ra
# Retrieve the sizes of the groups AFTER potentially swapping Ra and Rb
Sa = size[Ra]
Sb = size[Rb]
# Case 1: The group rooted at Ra is strictly smaller than the group rooted at Rb
if Sa < Sb:
# Merge Ra's group into Rb's group.
# According to the rules, members of the smaller group (Ra's group) are eliminated
# as potential leaders. Their probability becomes 0.
for k in members[Ra]:
prob[k] = 0
# Transfer the list of members from Ra's group to Rb's group.
# list.extend is generally efficient for this.
members[Rb].extend(members[Ra])
# Clear the member list for Ra. Reassigning to an empty list is efficient in Python.
members[Ra] = []
# Update the DSU structure: set Ra's parent to Rb and update Rb's size.
parent[Ra] = Rb
size[Rb] += Sa
# The size entry for Ra is now irrelevant as it's no longer a root.
# Case 2: The groups have equal size
else: # Sa == Sb
# Merge Ra's group into Rb's group (arbitrary choice, could be Rb into Ra).
# When equal-sized groups merge, the probabilities of members in BOTH groups are halved.
# Halve probabilities for members originally in Ra's group
for k in members[Ra]:
prob[k] = (prob[k] * inv2) % MOD
# Halve probabilities for members originally in Rb's group
for k in members[Rb]:
prob[k] = (prob[k] * inv2) % MOD
# Transfer members from Ra's list to Rb's list
members[Rb].extend(members[Ra])
# Clear Ra's list
members[Ra] = []
# Update the DSU structure: set Ra's parent to Rb and update Rb's size.
parent[Ra] = Rb
size[Rb] += Sa
# The size entry for Ra is now irrelevant.
# Main function to orchestrate the process
def solve():
"""
Reads input, initializes data structures, processes merges, and prints results.
"""
global parent, size, prob, members # Ensure access to global variables
# Read number of students (N) and number of merge operations (M)
N, M = map(int, sys.stdin.readline().split())
# Initialize DSU structure, probabilities, and member lists
# Using 1-based indexing for students (1 to N), so arrays are size N+1. Index 0 is unused.
parent = [i for i in range(N + 1)]
size = [1] * (N + 1)
prob = [0] * (N + 1) # Initialize probability array; will set prob[1..N] to 1
members = [[] for _ in range(N + 1)] # Initialize list of lists for members
# Set up initial state: each student is in their own group of size 1,
# is the leader of that group with probability 1.
for i in range(1, N + 1):
prob[i] = 1
members[i].append(i) # Student i is initially the only member of the group rooted at i
# Process all M merge operations sequentially
for _ in range(M):
# Read the pair of students (a, b) involved in the current merge operation
a, b = map(int, sys.stdin.readline().split())
# Perform the unite operation on the groups containing a and b
unite(a, b)
# After processing all merges, output the final probability for each student
for i in range(1, N + 1):
print(prob[i])
# Execute the main solver function
solve()