結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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
}
0