結果
| 問題 |
No.1341 真ん中を入れ替えて門松列
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 11,492 bytes |
| コンパイル時間 | 1,184 ms |
| コンパイル使用メモリ | 96,408 KB |
| 実行使用メモリ | 598,672 KB |
| 最終ジャッジ日時 | 2025-05-14 13:22:33 |
| 合計ジャッジ時間 | 5,110 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 2 MLE * 1 -- * 11 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include <cassert> // Include assert header for assertions
#include <limits> // Include limits header for numeric_limits
// Include or paste the AtCoder Library's Min Cost Flow implementation here.
// The following is a basic structure based on common implementations.
// Ensure this matches the library version available in your environment.
#ifndef ATCODER_MINCOSTFLOW_HPP // Guard against multiple includes
#define ATCODER_MINCOSTFLOW_HPP
#include <vector>
#include <limits>
#include <queue>
#include <utility> // For std::pair
namespace atcoder {
// Template for Min Cost Flow graph
// Cap: Type for capacity (e.g., int, long long)
// Cost: Type for cost (e.g., int, long long)
template <class Cap, class Cost>
struct mcf_graph {
public:
// Constructor for a graph with n vertices (0 to n-1)
mcf_graph(int n) : _n(n), g(n) {}
// Adds a directed edge from 'from' to 'to' with capacity 'cap' and cost 'cost'.
// Returns the index of the edge.
int add_edge(int from, int to, Cap cap, Cost cost) {
assert(0 <= from && from < _n); // Check vertex bounds
assert(0 <= to && to < _n);
assert(0 <= cap); // Capacity must be non-negative
// Store position for potential get_edge function
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
// Add edge and its reverse edge for residual graph
int from_id = int(g[from].size());
int to_id = int(g[to].size());
// Handle self-loop case correctly for reverse edge index
if (from == to) to_id++;
g[from].push_back({to, to_id, cap, cost});
g[to].push_back({from, from_id, 0, -cost}); // Reverse edge has 0 capacity initially
return m;
}
// Computes the minimum cost flow from source 's' to sink 't'.
// Returns a pair {flow, cost}. Finds max flow possible if flow_limit is max().
std::pair<Cap, Cost> flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
// Computes the minimum cost flow from 's' to 't' up to 'flow_limit'.
// Returns the pair {achieved_flow, min_cost_for_that_flow}.
std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
// Utilizes the slope function which computes costs for increasing flows.
// The last element of the result contains the flow and cost for the maximum flow achieved up to the limit.
std::vector<std::pair<Cap, Cost>> slope_result = slope(s, t, flow_limit);
if (slope_result.empty()) return {0, 0}; // Should technically not happen if graph created
return slope_result.back();
}
// Computes the minimum cost for flows 0, 1, ..., up to flow_limit.
// Returns a vector of pairs {flow, cost}. Useful for analyzing cost changes.
std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n); // Check vertex bounds
assert(0 <= t && t < _n);
assert(s != t); // Source and sink must be different
std::vector<Cost> dual(_n, 0), dist(_n); // Dual variables (potentials) and distances
std::vector<int> pv(_n), pe(_n); // Previous vertex and edge indices for path reconstruction
using P = std::pair<Cost, int>; // Pair {distance, vertex} for priority queue
Cap flow = 0;
Cost cost = 0;
std::vector<std::pair<Cap, Cost>> result;
result.push_back({flow, cost}); // Initial state: flow 0, cost 0
// Primal-Dual algorithm using potentials and Dijkstra
while (flow < flow_limit) {
// Initialize distances for Dijkstra
std::fill(dist.begin(), dist.end(), std::numeric_limits<Cost>::max());
dist[s] = 0;
// Priority queue for Dijkstra's algorithm
std::priority_queue<P, std::vector<P>, std::greater<P>> que;
que.push({0, s});
// Dijkstra on residual graph with reduced costs (cost + potential_diff)
while (!que.empty()) {
P p = que.top();
que.pop();
Cost cur_dist = p.first;
int v = p.second;
// Skip if we found a shorter path already
if (dist[v] < cur_dist) continue;
// Explore neighbors
for (int i = 0; i < int(g[v].size()); i++) {
auto e = g[v][i];
// Edge must have residual capacity
if (e.cap == 0) continue;
// Reduced cost: original cost + potential(u) - potential(v)
Cost cost2 = e.cost + dual[v] - dual[e.to];
// Relaxation step
if (dist[e.to] > dist[v] + cost2) {
dist[e.to] = dist[v] + cost2;
pv[e.to] = v; // Store predecessor
pe[e.to] = i; // Store edge index
que.push({dist[e.to], e.to});
}
}
}
// If sink 't' is unreachable, no more augmenting paths exist
if (dist[t] == std::numeric_limits<Cost>::max()) {
break;
}
// Update potentials (dual variables) based on shortest path distances
for (int v = 0; v < _n; v++) {
if (dist[v] == std::numeric_limits<Cost>::max()) continue;
// Potential update ensures non-negative reduced costs for next iteration
dual[v] += dist[v];
}
// Find bottleneck capacity 'd' along the augmenting path
Cap d = flow_limit - flow;
for (int v = t; v != s; v = pv[v]) {
d = std::min(d, g[pv[v]][pe[v]].cap);
}
// Safety check: Avoid loop if bottleneck capacity is 0
if (d == 0) break;
// Augment flow along the path
flow += d;
// Update total cost using potentials. dual[t] contains the shortest path cost in terms of original costs.
cost += d * dual[t];
// Update residual capacities along the path and its reverse edges
for (int v = t; v != s; v = pv[v]) {
auto& e = g[pv[v]][pe[v]];
e.cap -= d; // Decrease capacity of forward edge
g[v][e.rev].cap += d; // Increase capacity of reverse edge
}
result.push_back({flow, cost}); // Record the state (flow, cost)
}
return result; // Return the history of (flow, cost) pairs
}
private:
int _n; // Number of vertices
// Internal representation of an edge
struct _edge {
int to; // Destination vertex
int rev; // Index of the reverse edge in the adjacency list of 'to'
Cap cap; // Residual capacity
Cost cost; // Cost of the edge
};
std::vector<std::pair<int, int>> pos; // Stores {vertex, edge_index} for edge retrieval? Not strictly needed for flow calculation.
std::vector<std::vector<_edge>> g; // Adjacency list representation of the graph
};
} // namespace atcoder
#endif // ATCODER_MINCOSTFLOW_HPP
// Main problem-solving code starts here
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long ll; // Use long long for potentially large values
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of triples
ll M; // Target Kadomatsu points sum
cin >> N >> M;
vector<ll> A(N), initial_B(N), C(N); // Store input triples
for (int i = 0; i < N; ++i) {
cin >> A[i] >> initial_B[i] >> C[i];
// The problem guarantees A_i != C_i
}
// Setup Min Cost Flow graph
// Nodes: 0=Source(S), 1..N=Position nodes(P_i), N+1..2N=Value nodes(V_j), 2N+1=Sink(T)
int S = 0;
int T = 2 * N + 1;
// Initialize graph with 2N+2 vertices
atcoder::mcf_graph<int, ll> graph(2 * N + 2); // Capacity type int (always 1), Cost type ll
// Add edges from Source S to each Position node P_i
// Each position needs to be matched exactly once.
for (int i = 0; i < N; ++i) {
graph.add_edge(S, i + 1, 1, 0); // Edge S -> P_i (node i+1), capacity 1, cost 0
}
// Add edges from each Value node V_j to Sink T
// Each B value can be used at most once.
for (int j = 0; j < N; ++j) {
graph.add_edge(N + 1 + j, T, 1, 0); // Edge V_j (node N+1+j) -> T, capacity 1, cost 0
}
// Add edges between Position nodes P_i and Value nodes V_j if (A_i, B_j, C_i) is a Kadomatsu sequence
for (int i = 0; i < N; ++i) { // Iterate through positions i (node i+1)
for (int j = 0; j < N; ++j) { // Iterate through values B_j (node N+1+j)
ll current_A = A[i];
ll current_C = C[i];
ll current_B = initial_B[j]; // B value from the j-th original triple
ll L = min(current_A, current_C);
ll R = max(current_A, current_C);
// Check Kadomatsu condition: B must be distinct from A and C, and B must not be the median.
// Simplified condition: B < L or B > R. This implicitly covers distinctness B != A, B != C since A != C.
if (current_B < L || current_B > R) {
// If Kadomatsu condition holds, calculate the point value
ll point;
if (current_B < L) {
// If B is the minimum, max value is R = max(A, C)
point = R;
} else { // current_B > R
// If B is the maximum, max value is B
point = current_B;
}
// The cost of the edge is the negative of the point value
// We want to maximize total points, which is equivalent to minimizing the sum of negative points.
ll cost = -point;
// Add edge from P_i to V_j with capacity 1 and calculated cost
graph.add_edge(i + 1, N + 1 + j, 1, cost);
}
// If not Kadomatsu, no edge is added for this pair (i, j).
}
}
// Compute the minimum cost for a flow of exactly N
// The flow function returns {achieved_flow, min_cost_for_that_flow}
// We request flow up to N.
pair<int, ll> result = graph.flow(S, T, N);
int flow_achieved = result.first; // The actual flow achieved (max flow up to N)
ll min_total_cost = result.second; // Minimum cost for the achieved flow
// Check if it's possible to make all N triples Kadomatsu sequences.
// This requires achieving a flow of N (matching all N positions to N unique values).
if (flow_achieved < N) {
// If flow is less than N, a perfect matching is not possible.
cout << "NO" << endl;
} else {
// If flow is N, it is possible. Output YES.
cout << "YES" << endl;
// Calculate the maximum total points achievable, which is -min_total_cost.
ll max_total_points = -min_total_cost;
// Check if the maximum points meet the threshold M.
if (max_total_points >= M) {
cout << "KADOMATSU!" << endl;
} else {
cout << "NO" << endl;
}
}
return 0; // Indicate successful execution
}