結果

問題 No.1669 パズル作成
ユーザー qwewe
提出日時 2025-05-14 13:25:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,699 bytes
コンパイル時間 916 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 266,336 KB
最終ジャッジ日時 2025-05-14 13:27:02
合計ジャッジ時間 15,443 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // For std::iota

// DSU structure
struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // Initialize each element as its own parent
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // Path compression
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Simple union: make root_i child of root_j. Union by size/rank could also be used.
            parent[root_i] = root_j;
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false); // Faster I/O
    std::cin.tie(NULL); // Untie cin from cout

    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<bool>> is_black(N, std::vector<bool>(N, false));
    DSU dsu(2 * N); // Rows 0 to N-1, Columns N to 2N-1

    for (int k = 0; k < M; ++k) {
        int r, c;
        std::cin >> r >> c;
        --r; --c; // 0-indexed
        dsu.unite(r, N + c); // Unite row r with column c
        is_black[r][c] = true;
    }

    long long cost_fixed = 0;
    std::vector<std::vector<int>> adj_G_prime(2 * N); // Adjacency list for graph G'

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (is_black[r][c]) {
                continue; // Skip black cells
            }
            // This is a white cell (r,c)
            int root_r = dsu.find(r); // Representative for row r
            int root_c_node = dsu.find(N + c); // Representative for column c

            if (root_r == root_c_node) {
                cost_fixed++; // Must use Operation X
            } else {
                // Add edge in G' between DSU component representatives
                adj_G_prime[root_r].push_back(root_c_node);
                adj_G_prime[root_c_node].push_back(root_r);
            }
        }
    }
    
    long long cost_non_bipartite_penalty = 0;
    std::vector<int> colors_for_G_prime(2 * N, -1); // -1: uncolored, 0: color 0, 1: color 1

    for (int i = 0; i < 2 * N; ++i) {
        // Iterate through all potential nodes of G' (which are DSU representatives)
        if (dsu.parent[i] == i && colors_for_G_prime[i] == -1) { 
            // If i is a DSU representative and its Connected Component in G' is not yet colored
            
            std::vector<int> q_bfs; // Queue for BFS for current CC of G'
            q_bfs.push_back(i);
            colors_for_G_prime[i] = 0; // Assign first color
            int head = 0; 
            bool conflict_in_current_cc = false;

            while(head < q_bfs.size()){
                int u_repr = q_bfs[head++]; // Current representative node from G'
                
                for(int v_repr : adj_G_prime[u_repr]){ 
                    // v_repr is a neighbor representative node in G'
                    if(colors_for_G_prime[v_repr] == -1){ // If neighbor not colored
                        colors_for_G_prime[v_repr] = 1 - colors_for_G_prime[u_repr]; // Assign opposite color
                        q_bfs.push_back(v_repr);
                    } else if(colors_for_G_prime[v_repr] == colors_for_G_prime[u_repr]){
                        // Edge connects two nodes of same color: non-bipartite
                        conflict_in_current_cc = true;
                    }
                }
            }
            
            if(conflict_in_current_cc){
                cost_non_bipartite_penalty++;
            }
        }
    }

    std::cout << cost_fixed + cost_non_bipartite_penalty << std::endl;

    return 0;
}
0