結果
| 問題 |
No.1950 片道きゃっちぼーる
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 552 ms / 3,000 ms |
| コード長 | 10,076 bytes |
| コンパイル時間 | 1,640 ms |
| コンパイル使用メモリ | 110,472 KB |
| 実行使用メモリ | 63,288 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:29 |
| 合計ジャッジ時間 | 11,124 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <vector>
#include <climits> // Not strictly needed, custom INF used
using namespace std;
// Define long long for convenience
typedef long long ll;
// Using a very small negative number to represent negative infinity for maximum position calculations.
// This value needs to be smaller than any possible coordinate result (-10^9 - 10^9 = -2*10^9).
// -4e18 is sufficiently small and avoids potential overflow issues with LLONG_MIN.
const ll INF = -4e18;
// Global variables for graph structure and Tarjan's algorithm results
vector<vector<int>> adj; // Adjacency list for the graph of people (nodes 0 to N-1)
map<ll, int> pos_to_idx; // Map from position X_i to index i for efficient lookup
vector<ll> X, A; // Store positions and throw distances for each person
int N; // Number of people
// Tarjan's algorithm variables
vector<int> dfn; // Discovery time during DFS
vector<int> low; // Lowest discovery time reachable from node u (including itself)
vector<int> scc_id; // Stores the ID of the Strongly Connected Component (SCC) each node belongs to
stack<int> S; // Stack used in Tarjan's algorithm to keep track of nodes in current DFS path
vector<bool> onStack; // Tracks if a node is currently on the stack S
int timer; // Timer for assigning discovery times
int scc_count; // Counter for the number of SCCs found
// SCC graph and Dynamic Programming variables
vector<vector<int>> scc_adj; // Adjacency list for the condensation graph (graph of SCCs)
vector<ll> scc_max_pos; // Stores the maximum final position achievable by a throw *originating* from within this SCC and landing directly on the ground
vector<ll> final_max_pos; // Stores the overall maximum final position reachable *starting* from any node in this SCC (memoized results for DP)
// Tarjan's algorithm implementation to find Strongly Connected Components
void tarjan(int u) {
dfn[u] = low[u] = timer++; // Assign discovery time and initial low-link value
S.push(u); // Push node onto stack
onStack[u] = true; // Mark node as on stack
// Iterate through neighbors of u in the graph
for (int v : adj[u]) {
if (dfn[v] == -1) { // If neighbor v has not been visited yet
tarjan(v); // Recursively call Tarjan on v
low[u] = min(low[u], low[v]); // Update low-link value of u based on subtree result
} else if (onStack[v]) { // If neighbor v is visited and still on the stack (indicates a back edge to an ancestor in DFS tree)
low[u] = min(low[u], dfn[v]); // Update low-link value of u using discovery time of v
}
}
// If u is the root of an SCC (its low-link value equals its discovery time)
if (low[u] == dfn[u]) {
// Pop nodes from stack until u is popped. All popped nodes form an SCC.
while (true) {
int w = S.top();
S.pop();
onStack[w] = false; // Mark node as off stack
scc_id[w] = scc_count; // Assign the current SCC ID to node w
if (u == w) break; // Stop when the root u is popped
}
scc_count++; // Increment SCC counter for the next SCC
}
}
// Dynamic Programming on the SCC graph (DAG) using memoized recursion
// Computes the maximum final position reachable starting from any node within SCC u_scc
ll get_max_pos(int u_scc) {
// If the result for this SCC is already computed, return the memoized value
if (final_max_pos[u_scc] != INF) {
return final_max_pos[u_scc];
}
// Initialize the maximum position with the local maximum found within this SCC
// (maximum position achieved by a throw originating in this SCC and landing on ground)
ll current_max = scc_max_pos[u_scc];
// Explore neighboring SCCs in the condensation graph
// The maximum position reachable is the max of local position and positions reachable through neighbors
for (int v_scc : scc_adj[u_scc]) {
current_max = max(current_max, get_max_pos(v_scc)); // Recursively compute for neighbor SCCs
}
// Memoize the computed result and return it
return final_max_pos[u_scc] = current_max;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read number of people
cin >> N;
// Resize vectors to hold data for N people
X.resize(N);
A.resize(N);
adj.resize(N);
// Read positions and populate the position-to-index map
for (int i = 0; i < N; ++i) {
cin >> X[i];
pos_to_idx[X[i]] = i; // Store mapping from coordinate X_i to index i
}
// Read throw distances
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Build the graph based on possible throws between people
for (int i = 0; i < N; ++i) {
// Calculate potential landing position for a throw to the right
ll target_pos_right = X[i] + A[i];
// Use map.find() to check if a person exists at the landing position
auto it_right = pos_to_idx.find(target_pos_right);
if (it_right != pos_to_idx.end()) { // If find() does not return end iterator, a person exists
int target_idx = it_right->second; // Get the index of the person at the landing spot
adj[i].push_back(target_idx); // Add a directed edge from person i to target_idx
}
// Calculate potential landing position for a throw to the left
ll target_pos_left = X[i] - A[i];
// Check if a person exists at this landing position
auto it_left = pos_to_idx.find(target_pos_left);
if (it_left != pos_to_idx.end()) {
int target_idx = it_left->second;
adj[i].push_back(target_idx); // Add edge i -> target_idx
}
}
// Initialize data structures for Tarjan's algorithm
dfn.assign(N, -1); // Initialize discovery times to -1 (unvisited)
low.assign(N, -1); // Initialize low-link values to -1
scc_id.assign(N, -1); // Initialize SCC IDs to -1
onStack.assign(N, false); // Initialize onStack status to false
timer = 0; // Reset DFS timer
scc_count = 0; // Reset SCC counter
// Run Tarjan's algorithm starting from each unvisited node to find all SCCs
for (int i = 0; i < N; ++i) {
if (dfn[i] == -1) { // If node i hasn't been visited yet
tarjan(i);
}
}
// Initialize data structures for the SCC graph and DP calculations
scc_adj.resize(scc_count); // Resize SCC adjacency list
scc_max_pos.assign(scc_count, INF); // Initialize local max positions to negative infinity
final_max_pos.assign(scc_count, INF); // Initialize memoized DP results to negative infinity
vector<pair<int, int>> scc_edge_list; // Temporary list to store edges between SCCs before removing duplicates
// Compute local maximum positions for each SCC and gather edges for the condensation graph
for (int u = 0; u < N; ++u) {
int u_scc = scc_id[u]; // Get the SCC ID of the current person u
// Evaluate throw to the right
ll target_pos_right = X[u] + A[u];
auto it_right = pos_to_idx.find(target_pos_right);
if (it_right == pos_to_idx.end()) { // If the landing spot is empty (ground)
// Update the maximum position achieved by a direct throw to ground from this SCC
scc_max_pos[u_scc] = max(scc_max_pos[u_scc], target_pos_right);
} else { // If the ball lands on another person v
int v = it_right->second;
int v_scc = scc_id[v]; // Get SCC ID of the target person v
if (u_scc != v_scc) { // If the edge connects two different SCCs
scc_edge_list.push_back({u_scc, v_scc}); // Add this edge to the list for the condensation graph
}
}
// Evaluate throw to the left
ll target_pos_left = X[u] - A[u];
auto it_left = pos_to_idx.find(target_pos_left);
if (it_left == pos_to_idx.end()) { // Lands on ground
scc_max_pos[u_scc] = max(scc_max_pos[u_scc], target_pos_left);
} else { // Lands on person v
int v = it_left->second;
int v_scc = scc_id[v];
if (u_scc != v_scc) { // Edge connects different SCCs
scc_edge_list.push_back({u_scc, v_scc});
}
}
}
// Build the final SCC adjacency list for the condensation graph, removing duplicate edges
sort(scc_edge_list.begin(), scc_edge_list.end()); // Sort edges to group duplicates together
scc_edge_list.erase(unique(scc_edge_list.begin(), scc_edge_list.end()), scc_edge_list.end()); // Remove consecutive duplicates
// Populate the scc_adj adjacency list from the unique edge list
for(const auto& edge : scc_edge_list) {
scc_adj[edge.first].push_back(edge.second);
}
// Compute the maximum final positions for all SCCs using the DP function.
// Call get_max_pos for each SCC; memoization handles overlapping computations efficiently.
for (int i = 0; i < scc_count; ++i) {
if(final_max_pos[i] == INF) // Check if not already computed by a previous recursive call
get_max_pos(i); // Compute the max final position for this SCC and potentially others it depends on
}
// Output the results for each person
for (int i = 0; i < N; ++i) {
// Retrieve the pre-computed maximum final position for the SCC containing person i
ll max_final_p = final_max_pos[scc_id[i]];
// Calculate the maximum positive displacement: max(0, FinalPosition - StartPosition)
// If max_final_p is INF (no path ends on ground), max(0LL, INF - X[i]) correctly yields 0 since INF is very negative.
// If max_final_p <= X[i], max positive displacement is 0. max(0LL, max_final_p - X[i]) yields 0.
// Otherwise, the positive displacement is max_final_p - X[i]. max(0LL, ...) correctly yields this value.
cout << max(0LL, max_final_p - X[i]) << "\n";
}
return 0;
}