結果
| 問題 |
No.1341 真ん中を入れ替えて門松列
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,010 bytes |
| コンパイル時間 | 892 ms |
| コンパイル使用メモリ | 92,872 KB |
| 実行使用メモリ | 491,296 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:42 |
| 合計ジャッジ時間 | 4,746 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 2 TLE * 1 -- * 11 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
// Use long long for costs and potentially large sums
using CostType = long long;
// Use a large enough value for infinity, ensuring it doesn't overflow during calculations
// std::numeric_limits<long long>::max() is about 9e18. Dividing by 4 should be safe.
const CostType INF_COST = std::numeric_limits<CostType>::max() / 4;
// Structure to represent an edge in the residual graph
struct Edge {
int to; // destination vertex
int capacity; // residual capacity
int reverse_edge_idx; // index of the reverse edge in the adjacency list of 'to' vertex
CostType cost; // cost of pushing 1 unit of flow through this edge
};
// Adjacency list representation of the graph
std::vector<std::vector<Edge>> graph;
// Potentials for Dijkstra algorithm (to handle negative costs)
std::vector<CostType> h;
// Shortest distance estimates from source
std::vector<CostType> dist;
// Store path information for augmentation: previous vertex and index of edge used to reach current vertex
std::vector<int> prev_v, prev_e_idx;
// Function to add an edge and its corresponding reverse edge to the graph
void add_edge(int u, int v, int cap, CostType cost) {
// Add edge from u to v
graph[u].push_back({v, cap, (int)graph[v].size(), cost});
// Add reverse edge from v to u. Initial capacity is 0. Cost is negated.
graph[v].push_back({u, 0, (int)graph[u].size() - 1, -cost});
}
// Compute Minimum Cost Flow from source 's' to sink 't' with required flow 'f'
// Uses Dijkstra with potentials based on Successive Shortest Path algorithm
// Returns the minimum cost to achieve flow 'f', or a large value (INF_COST * 2) if flow 'f' cannot be achieved.
CostType min_cost_flow(int s, int t, int f) {
CostType total_cost = 0; // Accumulates the total minimum cost
int V = graph.size(); // Number of vertices in the graph
h.assign(V, 0); // Initialize potentials to 0
int flow_pushed = 0; // Keep track of the total flow pushed so far
// Continue augmenting paths until the required flow 'f' is achieved
while (flow_pushed < f) {
// Initialize distances to infinity for all vertices
dist.assign(V, INF_COST);
// Initialize predecessors for path reconstruction
prev_v.assign(V, -1);
prev_e_idx.assign(V, -1);
dist[s] = 0; // Distance from source to itself is 0
// Priority queue for Dijkstra. Stores pairs {distance, vertex}. Ordered by distance.
std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> pq;
pq.push({0, s}); // Start Dijkstra from source
while (!pq.empty()) {
// Extract vertex 'u' with the smallest distance 'd'
CostType d = pq.top().first;
int u = pq.top().second;
pq.pop();
// If we found a shorter path to 'u' already, skip this element
if (d > dist[u]) continue;
// Explore neighbors of 'u'
for (size_t i = 0; i < graph[u].size(); ++i) {
Edge &e = graph[u][i];
// Check if edge has residual capacity
if (e.capacity > 0) {
// Calculate reduced cost: cost' = original_cost + potential[u] - potential[v]
CostType reduced_cost = e.cost + h[u] - h[e.to];
// If found a shorter path to e.to using edge e
if (dist[e.to] > dist[u] + reduced_cost) {
dist[e.to] = dist[u] + reduced_cost; // Update distance
prev_v[e.to] = u; // Store predecessor
prev_e_idx[e.to] = i; // Store edge index
pq.push({dist[e.to], e.to}); // Add/update neighbor in priority queue
}
}
}
}
// If sink 't' is unreachable from 's' in the residual graph, we cannot push more flow
if (dist[t] == INF_COST) {
// Cannot satisfy the required flow 'f'
return INF_COST * 2; // Return a large value indicating failure
}
// Update potentials using the shortest path distances found by Dijkstra
// h[v] += dist[v] maintains non-negative reduced costs for the next iteration
for (int v = 0; v < V; ++v) {
if (dist[v] != INF_COST) { // Only update potentials for reachable vertices
h[v] += dist[v];
}
}
// Determine the bottleneck capacity ('flow_on_path') along the shortest path found
int flow_on_path = f - flow_pushed; // Maximum flow we need is the remaining required flow
// Trace back path from t to s to find bottleneck capacity
for (int v = t; v != s; v = prev_v[v]) {
flow_on_path = std::min(flow_on_path, graph[prev_v[v]][prev_e_idx[v]].capacity);
}
// Increase total flow pushed
flow_pushed += flow_on_path;
// Add the cost of pushing 'flow_on_path' units along this path to the total cost.
// The cost of the path in terms of original costs is given by the potential difference h[t] - h[s]. Since h[s] remains 0, it's just h[t].
total_cost += (CostType)flow_on_path * h[t];
// Update residual capacities along the path and reverse edges
for (int v = t; v != s; v = prev_v[v]) {
Edge &e = graph[prev_v[v]][prev_e_idx[v]];
e.capacity -= flow_on_path; // Decrease capacity of forward edge
graph[v][e.reverse_edge_idx].capacity += flow_on_path; // Increase capacity of reverse edge
}
}
// Successfully pushed flow 'f'
return total_cost;
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of triplets
long long M; // Threshold for Kadomatsu point sum
std::cin >> N >> M;
// Store input triplets A, B, C values
std::vector<long long> A(N), C(N);
std::vector<long long> B(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i] >> B[i] >> C[i];
}
// Set up the flow network graph
// V = total vertices: Source (0) + N slot nodes (1..N) + N value nodes (N+1..2N) + Sink (2N+1)
int V = 2 * N + 2;
graph.resize(V);
int s = 0, t = 2 * N + 1; // Source and sink node indices
// Add edges from source to slot nodes
// Each slot node corresponds to a triplet (A_i, ?, C_i)
for (int i = 0; i < N; ++i) {
add_edge(s, i + 1, 1, 0); // Capacity 1, Cost 0
}
// Add edges from value nodes to sink
// Each value node corresponds to a B_j value
for (int j = 0; j < N; ++j) {
add_edge(N + 1 + j, t, 1, 0); // Capacity 1, Cost 0
}
// Add edges between slot nodes and value nodes if the assignment forms a Kadomatsu sequence
for (int i = 0; i < N; ++i) { // Slot i corresponds to node i+1
long long min_AC = std::min(A[i], C[i]);
long long max_AC = std::max(A[i], C[i]);
for (int j = 0; j < N; ++j) { // Value B[j] corresponds to node N+1+j
// Check Kadomatsu condition: B[j] must be outside the interval [min(A[i], C[i]), max(A[i], C[i])]
if (B[j] < min_AC) {
// Condition met: B[j] < min(A[i], C[i])
// Kadomatsu point is max(A[i], B[j], C[i]) = max(A[i], C[i]) = max_AC
CostType weight = max_AC;
add_edge(i + 1, N + 1 + j, 1, -weight); // Use negative weight because we want to maximize total weight via min cost flow
} else if (B[j] > max_AC) {
// Condition met: B[j] > max(A[i], C[i])
// Kadomatsu point is max(A[i], B[j], C[i]) = B[j]
CostType weight = B[j];
add_edge(i + 1, N + 1 + j, 1, -weight); // Use negative weight
}
// If B[j] is within [min_AC, max_AC], it's not a Kadomatsu sequence, so no edge is added.
}
}
// Calculate minimum cost for achieving flow N (which corresponds to a perfect matching)
CostType min_total_cost = min_cost_flow(s, t, N);
// Check if it was possible to achieve flow N (i.e., find a perfect matching)
if (min_total_cost >= INF_COST * 2) { // Check against the failure indicator value
// A perfect matching doesn't exist. Output NO.
std::cout << "NO" << std::endl;
} else {
// A perfect matching exists. Output YES.
std::cout << "YES" << std::endl;
// Maximum total weight is the negation of the minimum cost found
long long max_total_weight = -min_total_cost;
// Check if the maximum weight meets the threshold M
if (max_total_weight >= M) {
std::cout << "KADOMATSU!" << std::endl;
} else {
std::cout << "NO" << std::endl;
}
}
return 0;
}