結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 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 }