結果

問題 No.408 五輪ピック
ユーザー qwewe
提出日時 2025-05-14 13:03:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 418 ms / 5,000 ms
コード長 5,477 bytes
コンパイル時間 1,047 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:05:37
合計ジャッジ時間 3,426 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility> // For std::pair

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

    int N; // Number of vertices
    int M; // Number of edges
    std::cin >> N >> M;

    // Adjacency list representation of the graph. adj[i] stores neighbors of vertex i.
    // Vertices are 1-indexed, so we use size N+1.
    std::vector<std::vector<int>> adj(N + 1);
    
    // Store all edges to iterate through them later.
    // Using std::pair to store edges {u, v}.
    std::vector<std::pair<int, int>> edges;
    // Reserve memory upfront to avoid reallocations during push_back.
    edges.reserve(M); 

    for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        // Add edge to adjacency lists for both vertices.
        adj[u].push_back(v);
        adj[v].push_back(u);
        // Store the edge pair.
        edges.push_back({u, v});
    }

    // A boolean vector to quickly check if a vertex is a neighbor of vertex 1.
    // is_neighbor_of_1[i] is true if vertex i is adjacent to vertex 1.
    std::vector<bool> is_neighbor_of_1(N + 1, false);
    // Check if N >= 1 before accessing adj[1]. The constraints N >= 2 guarantee vertex 1 exists.
    if (N >= 1) { 
       // Populate the boolean vector based on neighbors of vertex 1.
       for (int neighbor : adj[1]) {
           // Add basic bounds check for robustness, though constraints guarantee 1 <= neighbor <= N.
           if (neighbor >= 1 && neighbor <= N) { 
               is_neighbor_of_1[neighbor] = true;
           }
       }
    }

    // Temporary vectors to store potential candidates for v2 and v5.
    // Declared outside the loop to potentially reuse allocated memory.
    std::vector<int> potential_v2; 
    std::vector<int> potential_v5; 

    // Iterate through each edge {u, v} in the graph.
    // This edge could be the middle edge (v3, v4) of a potential 5-cycle containing vertex 1.
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        
        // In a simple cycle 1 -> v2 -> v3 -> v4 -> v5 -> 1, vertices v3 and v4 cannot be vertex 1.
        if (u == 1 || v == 1) continue;

        // We need to check both orientations for the edge {u, v}:
        // Case 1: u plays the role of v3, v plays the role of v4.
        potential_v2.clear(); // Clear the vector before populating
        // Find neighbors 'x' of 'u' (v3) that are also neighbors of 1. These are candidates for v2.
        for (int x : adj[u]) { 
            // Added bounds check for safety. is_neighbor_of_1 ensures x is neighbor of 1.
            if (x >= 1 && x <= N && is_neighbor_of_1[x]) { 
                 potential_v2.push_back(x);
            }
        }

        potential_v5.clear(); // Clear the vector before populating
        // Find neighbors 'y' of 'v' (v4) that are also neighbors of 1. These are candidates for v5.
        for (int y : adj[v]) { 
             // Added bounds check for safety. is_neighbor_of_1 ensures y is neighbor of 1.
             if (y >= 1 && y <= N && is_neighbor_of_1[y]) { 
                 potential_v5.push_back(y);
            }
        }

        // Check all pairs of (v2, v5) candidates.
        for (int v2 : potential_v2) {
            for (int v5 : potential_v5) {
                 // Cycle candidate: 1 -> v2 -> u -> v -> v5 -> 1
                 // Check the distinctness condition for a simple cycle.
                 // Vertices 1, v2, u, v, v5 must all be distinct.
                 // From construction and checks so far: 1 != u, 1 != v, 1 != v2, 1 != v5. Also u != v.
                 // From edges existing in simple graph: v2 != u, v != v5.
                 // The remaining distinctness checks required are: v2 != v, v2 != v5, u != v5.
                 if (v2 != v && v2 != v5 && u != v5) {
                      std::cout << "YES" << std::endl;
                      return 0; // Found a 5-cycle, output YES and terminate.
                 }
            }
        }
        
        // Case 2: v plays the role of v3, u plays the role of v4 (symmetric check).
        // This handles the cycle in the opposite direction or simply assigning roles differently.
        potential_v2.clear(); // Reuse vector, clear first. Now finding neighbors of v (as v3)
         for (int x : adj[v]) { 
            if (x >= 1 && x <= N && is_neighbor_of_1[x]) { 
                 potential_v2.push_back(x);
            }
        }
        
        potential_v5.clear(); // Reuse vector, clear first. Now finding neighbors of u (as v4)
        for (int y : adj[u]) { 
             if (y >= 1 && y <= N && is_neighbor_of_1[y]) { 
                 potential_v5.push_back(y);
            }
        }

        // Check all pairs of (v2, v5) candidates for this orientation.
        for (int v2 : potential_v2) {
            for (int v5 : potential_v5) {
                 // Cycle candidate: 1 -> v2 -> v -> u -> v5 -> 1
                 // Check distinctness.
                 // Required checks for this orientation: v2 != u, v2 != v5, v != v5.
                 if (v2 != u && v2 != v5 && v != v5) {
                      std::cout << "YES" << std::endl;
                      return 0; // Found a 5-cycle, output YES and terminate.
                 }
            }
        }
    }

    // If the loop finishes without finding any 5-cycle containing vertex 1:
    std::cout << "NO" << std::endl;

    return 0;
}
0