結果
| 問題 |
No.1194 Replace
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,310 ms / 2,000 ms |
| コード長 | 13,773 bytes |
| コンパイル時間 | 1,882 ms |
| コンパイル使用メモリ | 120,500 KB |
| 実行使用メモリ | 117,436 KB |
| 最終ジャッジ日時 | 2025-05-14 13:01:43 |
| 合計ジャッジ時間 | 21,646 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
// Use long long for large integers to accommodate N up to 10^9 and sums up to N(N+1)/2
typedef long long ll;
// Global variables used across graph processing functions
vector<vector<int>> adj; // Adjacency list for the graph based on mapped indices
vector<int> dfn; // Discovery time in DFS (used in Tarjan's algorithm)
vector<int> low; // Lowest discovery time reachable from a node (used in Tarjan's algorithm)
vector<int> scc_id; // Stores the SCC ID assigned to each vertex (mapped index)
stack<int> S_tarjan; // Stack used by Tarjan's algorithm to keep track of visited nodes
vector<bool> onStack; // Tracks whether a vertex is currently on the Tarjan's stack
int timer; // Counter for assigning discovery times during DFS
int scc_count; // Counter for the number of Strongly Connected Components found
vector<ll> idx_to_val; // Maps an internal index (0 to num_vertices-1) back to its original potentially large integer value
vector<vector<int>> adj_scc; // Adjacency list for the condensation graph (graph of SCCs)
vector<ll> MaxVal; // Stores the maximum original value found within each SCC
vector<ll> memo; // Memoization table for the DP calculation on the condensation graph (-1 indicates value not computed yet)
/**
* @brief Performs Tarjan's algorithm to find Strongly Connected Components (SCCs) in the graph.
*
* @param u The current vertex index being visited.
*/
void tarjan(int u) {
dfn[u] = low[u] = ++timer; // Initialize discovery time and low-link value for vertex u
S_tarjan.push(u); // Push vertex u onto the stack
onStack[u] = true; // Mark vertex u as being on the stack
// Iterate through all neighbors v of vertex u in the graph
for (int v : adj[u]) {
if (dfn[v] == 0) { // If neighbor v has not been visited yet (dfn[v] == 0)
tarjan(v); // Recursively call Tarjan's algorithm on v
// After returning from the recursive call for v, update the low-link value of u.
// u can reach whatever v can reach.
low[u] = min(low[u], low[v]);
} else if (onStack[v]) { // If neighbor v has been visited and is still on the stack
// This indicates a back edge to an ancestor in the DFS tree, closing a cycle.
// Update the low-link value of u based on the discovery time of v.
// We use dfn[v] here because v is an ancestor already on the stack.
low[u] = min(low[u], dfn[v]);
}
}
// Check if vertex u is the root of an SCC
// This happens if its low-link value is equal to its discovery time.
if (low[u] == dfn[u]) {
// If u is a root, pop vertices from the stack until u is popped.
// All vertices popped belong to the same SCC.
while (true) {
int node = S_tarjan.top(); // Get the top vertex from the stack
S_tarjan.pop(); // Pop the vertex
onStack[node] = false; // Mark the vertex as removed from the stack
scc_id[node] = scc_count; // Assign the current SCC ID to this vertex
if (node == u) break; // Stop when the root u itself is popped
}
scc_count++; // Increment the SCC counter for the next SCC found
}
}
/**
* @brief Computes the maximum reachable value starting from a given SCC using Dynamic Programming with memoization.
*
* This function operates on the condensation graph, which is a Directed Acyclic Graph (DAG).
*
* @param scc_u The index (ID) of the starting SCC.
* @return The maximum value reachable from any vertex within SCC scc_u.
*/
ll computeMaxReachable(int scc_u) {
// If the result for this SCC has already been computed and stored in the memo table, return it directly.
if (memo[scc_u] != -1) {
return memo[scc_u];
}
// Initialize the maximum reachable value with the maximum value found intrinsically within the current SCC (`scc_u`).
ll max_reach_val = MaxVal[scc_u];
// Explore all SCCs (`scc_v`) that are directly reachable from `scc_u` in the condensation graph.
for (int scc_v : adj_scc[scc_u]) {
// Recursively call `computeMaxReachable` for the neighbor SCC `scc_v`.
// Update `max_reach_val` if the value reachable through `scc_v` is greater.
max_reach_val = max(max_reach_val, computeMaxReachable(scc_v));
}
// Store the computed maximum reachable value in the memoization table before returning it.
return memo[scc_u] = max_reach_val;
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll N; // Length of the array A
int M; // Number of candidate operations
cin >> N >> M;
vector<pair<ll, ll>> ops(M); // Stores the M operations as pairs (B_i, C_i)
set<ll> involved_vals_set; // A set to efficiently collect unique values appearing in operations (either as B_i or C_i)
set<ll> sources_set; // A set to efficiently collect unique source values (B_i) of the operations
// Read the M operations from input
for (int i = 0; i < M; ++i) {
cin >> ops[i].first >> ops[i].second; // Read B_i and C_i
// Add both B_i and C_i to the set of involved values
involved_vals_set.insert(ops[i].first);
involved_vals_set.insert(ops[i].second);
// Add B_i to the set of source values
sources_set.insert(ops[i].first);
}
// Since original values (B_i, C_i) can be large (up to N=10^9), we map them
// to contiguous integer indices [0, num_vertices-1] to build a manageable graph.
map<ll, int> val_to_idx; // Maps original value to its internal index
// `idx_to_val` is populated during mapping to allow retrieval of original values later
idx_to_val.reserve(involved_vals_set.size()); // Reserve capacity for efficiency
int current_idx = 0; // Counter for assigning indices
// Convert the set of involved values to a vector to ensure consistent iteration order for mapping
vector<ll> involved_vals_vec(involved_vals_set.begin(), involved_vals_set.end());
for (ll val : involved_vals_vec) {
val_to_idx[val] = current_idx; // Assign index `current_idx` to value `val`
idx_to_val.push_back(val); // Store `val` at index `current_idx` in the reverse map
current_idx++; // Move to the next index
}
int num_vertices = current_idx; // The total number of unique values involved gives the number of vertices in our graph
// Proceed with graph algorithms only if there are operations involving values (num_vertices > 0)
if (num_vertices > 0) {
// Build the adjacency list `adj` for the graph using the mapped indices
adj.resize(num_vertices);
for (int i = 0; i < M; ++i) {
// Check if both B_i and C_i exist in our map (they should, by construction)
if (val_to_idx.count(ops[i].first) && val_to_idx.count(ops[i].second)) {
int u = val_to_idx[ops[i].first]; // Get the index for B_i
int v = val_to_idx[ops[i].second]; // Get the index for C_i
adj[u].push_back(v); // Add a directed edge from u to v
}
}
// Initialize data structures needed for Tarjan's algorithm
dfn.assign(num_vertices, 0); // Initialize discovery times to 0 (meaning unvisited)
low.assign(num_vertices, 0); // Initialize low-link values to 0
scc_id.assign(num_vertices, -1); // Initialize SCC IDs to -1 (meaning no SCC assigned yet)
onStack.assign(num_vertices, false); // Initialize onStack status for all vertices to false
// Ensure the Tarjan stack is empty before starting (important if reusing these globals, e.g., multiple test cases)
while (!S_tarjan.empty()) S_tarjan.pop();
timer = 0; // Reset the timer for discovery times
scc_count = 0; // Reset the SCC counter
// Run Tarjan's algorithm starting from each vertex that hasn't been visited yet
for (int i = 0; i < num_vertices; ++i) {
if (dfn[i] == 0) { // If vertex i is unvisited
tarjan(i); // Start Tarjan's DFS from vertex i
}
}
// Proceed only if at least one SCC was found (scc_count > 0)
if (scc_count > 0) {
// Compute the maximum original value (`MaxVal`) present within each identified SCC
MaxVal.assign(scc_count, 0); // Initialize MaxVal for each SCC to 0
for (int i = 0; i < num_vertices; ++i) {
// Check if vertex i has been assigned to a valid SCC
if (scc_id[i] != -1) {
// Update the maximum value for the SCC that vertex i belongs to
MaxVal[scc_id[i]] = max(MaxVal[scc_id[i]], idx_to_val[i]);
}
}
// Build the condensation graph (`adj_scc`) where each node represents an SCC
adj_scc.resize(scc_count);
set<pair<int, int>> scc_edges; // Use a set to store edges between SCCs to automatically handle duplicates
// Iterate through all vertices u and their neighbors v in the original graph
for (int u = 0; u < num_vertices; ++u) {
// Skip if vertex u was not assigned to an SCC (should not happen if graph is connected/processed correctly)
if (scc_id[u] == -1) continue;
for (int v : adj[u]) {
// Skip if neighbor v was not assigned to an SCC
if (scc_id[v] == -1) continue;
// If vertex u and vertex v belong to different SCCs
if (scc_id[u] != scc_id[v]) {
// Check if an edge between these SCCs has already been added
if (scc_edges.find({scc_id[u], scc_id[v]}) == scc_edges.end()) {
// If not, add a directed edge from the SCC of u to the SCC of v in the condensation graph
adj_scc[scc_id[u]].push_back(scc_id[v]);
// Record this edge in the set to prevent adding it again
scc_edges.insert({scc_id[u], scc_id[v]});
}
}
}
}
// Compute the maximum reachable value for each SCC using Dynamic Programming on the DAG (condensation graph)
memo.assign(scc_count, -1); // Initialize the memoization table with -1 (indicating not computed)
// Iterate through all SCCs
for (int i = 0; i < scc_count; ++i) {
// If the max reachable value for SCC i hasn't been computed yet
if (memo[i] == -1) {
// Call the recursive DP function to compute it
computeMaxReachable(i);
}
}
}
}
// Calculate the initial sum of the array A = [1, 2, ..., N]
// Initial sum is Sum(i for i=1 to N) = N*(N+1)/2.
// Use 128-bit integer type for the intermediate product N*(N+1) to prevent overflow,
// as N can be up to 10^9, N*(N+1) can exceed 64 bits.
// The final result after dividing by 2 will fit within a 64-bit signed long long.
ll total_sum;
if (N == 0) {
total_sum = 0; // Handle N=0 edge case (though problem constraints state N>=2)
} else {
// Calculate N*(N+1) using 128 bits, then divide by 2
unsigned __int128 temp_sum = (unsigned __int128)N * (N + 1) / 2;
total_sum = (ll)temp_sum; // Cast the result back to long long (which is guaranteed to fit)
}
// Calculate the total change (`delta_sum`) to the initial sum caused by the operations.
// For each initial value `k` that is a source (B_i) of some operation,
// we find the maximum value `max_k` it can be transformed into,
// and add the difference (`max_k - k`) to the total change.
ll delta_sum = 0;
// Only calculate the delta sum if SCCs were actually processed (scc_count > 0)
if (scc_count > 0) {
// Iterate through each unique source value `k` identified earlier
for (ll k : sources_set) {
// Check if this source value `k` was actually involved in the graph (it should be)
if (val_to_idx.count(k)) {
int idx = val_to_idx[k]; // Get the mapped index for k
// Ensure that the index `idx` is valid and has been assigned a valid SCC ID
// Check `idx < scc_id.size()` prevents out-of-bounds access if idx is somehow invalid
if (idx < scc_id.size() && scc_id[idx] != -1) {
int scc_k = scc_id[idx]; // Get the SCC ID for the SCC containing k
// Ensure the SCC ID `scc_k` is a valid index for the memoization table `memo`
if (scc_k < memo.size()) {
// Retrieve the pre-computed maximum reachable value from the SCC containing k
ll max_k = memo[scc_k];
// Add the change (max reachable value - initial value k) to the total delta sum
delta_sum += (max_k - k);
}
}
}
}
}
// The final maximum possible sum is the initial sum plus the total calculated change (delta_sum)
total_sum += delta_sum;
// Output the final result
cout << total_sum << endl;
return 0;
}