結果

問題 No.3071 Double Speedrun
ユーザー qwewe
提出日時 2025-05-14 12:59:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,758 bytes
コンパイル時間 741 ms
コンパイル使用メモリ 86,092 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:00:22
合計ジャッジ時間 1,524 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int L, R, M;
    // Read the number of vertices in V1 (L), V2 (R), and the number of edges (M)
    std::cin >> L >> R >> M;

    // Check constraints for dimensions. Problem statement guarantees L, R >= 1, M >= 1.
    // If L=0 or R=0, it might violate bipartite graph definition or constraints. Assuming valid inputs.

    // Store the edges. Each edge connects a vertex from V1 (0..L-1) and V2 (0..R-1).
    // We will map vertices from V2 to indices L..L+R-1 for a unified vertex index space 0..L+R-1.
    std::vector<std::pair<int, int>> edges(M);
    // Store the degree of each vertex. Initialize all degrees to 0.
    std::vector<int> degree(L + R, 0);

    // Read M edges from input
    for (int i = 0; i < M; ++i) {
        int u, v_raw; // u is vertex index in V1, v_raw is vertex index in V2
        std::cin >> u >> v_raw;
        
        // Assuming 0-based indexing based on constraints 0 <= a_i < L, 0 <= b_i < R.
        // Map vertex index from V2 (v_raw) to the unified index space [L, L+R-1]
        int v = L + v_raw; 
        // Store the edge with unified indices
        edges[i] = {u, v}; 
        // Increment degrees of the connected vertices
        degree[u]++;       
        degree[v]++;       
    }

    // Compute the minimum degree (delta) of the graph.
    // Initialize delta with a value larger than any possible degree (e.g., M+1).
    int delta = M + 1; 
    
    // The problem states "孤立点は存在しない" (isolated vertices do not exist).
    // This implies that every vertex in V1 U V2 must have a degree of at least 1.
    // Find the minimum degree among all L+R vertices.
    for (int i = 0; i < L + R; ++i) {
        // If degree[i] == 0, it contradicts the problem statement. Assume degree[i] >= 1 for all i.
        delta = std::min(delta, degree[i]);
    }
    
    // If L+R = 0, this loop doesn't run. But constraints L, R >= 1 ensure L+R >= 2.
    // If M = 0, degrees are all 0. But constraints M >= 1 ensure at least one edge.
    // Therefore, delta should be correctly computed and delta >= 1.

    // Vector to store the color assigned to each edge. Size M.
    std::vector<int> edge_colors(M);
    // Use a 2D vector `needed` to track which colors are still required for each vertex.
    // `needed[v][k]` is true if vertex `v` still needs an incident edge with color `k`.
    // Initialize all `needed` flags to true, meaning initially all vertices need all colors 0..delta-1.
    // Dimensions: (L+R) vertices x delta colors.
    std::vector<std::vector<bool>> needed(L + R, std::vector<bool>(delta, true));

    // Apply the greedy coloring strategy: Iterate through edges and assign colors.
    for (int i = 0; i < M; ++i) {
        int u = edges[i].first;  // First endpoint of the i-th edge
        int v = edges[i].second; // Second endpoint of the i-th edge

        int best_k = -1;    // Variable to store the best color found for the current edge
        int max_score = -1; // Variable to store the maximum score achieved by any color

        // Iterate through all possible colors k from 0 to delta-1
        for (int k = 0; k < delta; ++k) {
            // Calculate the score for color k. The score is the count of endpoints (u, v) that still need color k.
            // Score can be 0, 1, or 2.
            int current_score = (needed[u][k] ? 1 : 0) + (needed[v][k] ? 1 : 0);
            
            // If the current color k has a higher score than the max score found so far,
            // update max_score and set best_k to k.
            if (current_score > max_score) {
                max_score = current_score;
                best_k = k;
            } 
            // If current_score is equal to max_score, we apply a tie-breaking rule: choose the smallest k.
            // Since we iterate k from 0 upwards, the first k that achieves the max_score is automatically the smallest.
            // We only need to handle the initialization case where best_k is -1.
            // If max_score is 0 initially, the first k=0 will set max_score=0, best_k=0.
            // If subsequent k also have score 0, best_k remains 0 (the minimum).
            else if (current_score == max_score && best_k == -1) {
                 // Assign the first k encountered if max_score is 0 or hasn't been updated yet.
                 best_k = k;
            }
        }
        
        // After checking all colors, best_k holds the chosen color for edge i.
        // If delta is 0 (which shouldn't happen) or some other unexpected state leads to best_k = -1, default to color 0.
        if (best_k == -1) {
           best_k = 0; 
        }

        // Assign the chosen color to the current edge i
        edge_colors[i] = best_k; 
        // Update the 'needed' status for the endpoints u and v.
        // Once an edge of color best_k is incident to u (or v), they no longer strictly 'need' it 
        // for the purpose of maximizing the score in subsequent steps.
        // The final state must satisfy the condition that all vertices are incident to all colors.
        // The theorem guarantees this is possible, and this greedy strategy finds one such coloring.
        needed[u][best_k] = false; 
        needed[v][best_k] = false;
    }

    // Output the results.
    // First line: the maximum number of colors K used, which is delta.
    std::cout << delta << "\n";
    // Following M lines: the color assigned to each edge i (0-indexed color from 0..delta-1).
    for (int i = 0; i < M; ++i) {
        std::cout << edge_colors[i] << "\n";
    }

    return 0;
}
0