#1136276 (C++23) No.3321 岩井星人グラフ-1

• 問題: No.3321 岩井星人グラフ-1
• ユーザー: Neculapia
• 提出日時: 2025-11-25 09:09:00
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 11,183 bytes
• コンパイル時間: 5,055 ms
• コンパイル使用メモリ: 372,396 KB
• 実行使用メモリ: 28,696 KB
• 最終ジャッジ日時: 2025-11-25 09:09:15
• 合計ジャッジ時間: 14,529 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	WA * 3
other	WA * 89

コンパイルメッセージ

main.cpp: In member function ‘void Printer::flush()’:
main.cpp:121:20: warning: ignoring return value of ‘ssize_t write(int, const void*, size_t)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  121 |             ::write(fd, buf.data(), idx);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <unistd.h>
#include <ext/pb_ds/assoc_container.hpp>

#ifdef ATCODER
#include <atcoder/all>
#endif

using namespace std;
using namespace __gnu_pbds;
#ifdef ATCODER
using namespace atcoder;
#endif

using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
using pii = pair<i32, i32>;
using pll = pair<i64, i64>;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int INF32 = (1 << 30);
constexpr i64 INF64 = (i64(1) << 60);

struct Scanner {
    static constexpr size_t BUFSIZE = 1 << 20;
    int fd;
    size_t idx;
    size_t size;
    array<char, BUFSIZE> buf;

    Scanner(int fd_ = 0) : fd(fd_), idx(0), size(0) {}

    inline void refill() {
        size = ::read(fd, buf.data(), BUFSIZE);
        idx = 0;
    }

    inline char getch() {
        if (idx >= size) {
            refill();
            if (size == 0) return '\0';
        }
        return buf[idx++];
    }

    inline bool skip_space() {
        char c = getch();
        while (c <= ' ' && c != '\0') c = getch();
        if (c == '\0') return false;
        idx--;
        return true;
    }

    template<class T>
    bool read_signed(T &x) {
        if (!skip_space()) {
            x = 0;
            return false;
        }
        char c = getch();
        bool neg = false;
        if (c == '-') {
            neg = true;
            c = getch();
        }
        T val = 0;
        while ('0' <= c && c <= '9') {
            val = val * 10 + (c - '0');
            c = getch();
        }
        x = neg ? -val : val;
        return true;
    }

    template<class T>
    bool read_unsigned(T &x) {
        if (!skip_space()) {
            x = 0;
            return false;
        }
        char c = getch();
        T val = 0;
        while ('0' <= c && c <= '9') {
            val = val * 10 + (c - '0');
            c = getch();
        }
        x = val;
        return true;
    }

    bool read(i32 &x) { return read_signed<i32>(x); }
    bool read(i64 &x) { return read_signed<i64>(x); }
    bool read(u32 &x) { return read_unsigned<u32>(x); }
    bool read(u64 &x) { return read_unsigned<u64>(x); }
};

struct Printer {
    static constexpr size_t BUFSIZE = 1 << 20;
    int fd;
    size_t idx;
    array<char, BUFSIZE> buf;

    Printer(int fd_ = 1) : fd(fd_), idx(0) {}

    ~Printer() {
        flush();
    }

    inline void flush() {
        if (idx) {
            ::write(fd, buf.data(), idx);
            idx = 0;
        }
    }

    inline void put_char(char c) {
        if (idx == BUFSIZE) flush();
        buf[idx++] = c;
    }

    void write_str(string_view s) {
        for (char c : s) put_char(c);
    }

    template<class T>
    void print(const T &x) {
        if constexpr (is_same_v<T, string>) write_str(x);
        else if constexpr (is_integral_v<T>) {
            if (x < 0) { put_char('-'); write_unsigned(-x); }
            else write_unsigned(x);
        } else write_str("Printer Error");
        put_char('\n');
    }

    template<class T>
    void write_unsigned(T x) {
        if (x == 0) { put_char('0'); return; }
        char s[64]; int n = 0;
        while (x > 0) { s[n++] = char('0' + (x % 10)); x /= 10; }
        while (n--) put_char(s[n]);
    }
};

Scanner in;
Printer out;

#define rep(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define repi(i, a, b) for (i32 i = (i32)(a); i < (i32)(b); ++i)
#define sz(x) ((i32)(x).size())
#define all(x) begin(x), end(x)

template<class F>
struct RecLambda {
    F f;
    RecLambda(F f_) : f(move(f_)) {}
    template<class... Args>
    decltype(auto) operator()(Args &&...args) const {
        return f(*this, forward<Args>(args)...);
    }
};

bool solve_tree(int N, const V<V<int>>& adj, const V<int>& deg) {
    int c1 = 0, c2 = 0, c3 = 0;
    rep(i, N) {
        if (deg[i] == 1) c1++;
        else if (deg[i] == 2) c2++;
        else if (deg[i] == 3) c3++;
        else if (deg[i] > 3) return false;
    }
    int X = c1;
    if (X < 3) return false;
    if (N % X != 0) return false;
    int Y = N / X;
    if (c3 != X - 2) return false;
    if (c2 != N - 2 * X + 2) return false;

    V<int> d(N, -1);
    queue<int> q;
    rep(i, N) {
        if (deg[i] == 1) {
            d[i] = 0;
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (d[u] >= Y) return false;
        for (int v : adj[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    V<int> layer_cnt(Y, 0);
    rep(i, N) {
        if (d[i] == -1) return false;
        layer_cnt[d[i]]++;
    }

    rep(i, Y - 1) if (layer_cnt[i] != X) return false;
    if (layer_cnt[Y - 1] != X) return false;

    repi(i, 1, Y - 1) {
        rep(u, N) if (d[u] == i && deg[u] != 2) return false;
    }

    V<int> backbone;
    rep(u, N) if (d[u] == Y - 1) backbone.push_back(u);

    int edges_in_bb = 0;
    V<int> bb_deg(N, 0);
    for (int u : backbone) {
        for (int v : adj[u]) {
            if (d[v] == Y - 1) {
                if (u < v) edges_in_bb++;
                bb_deg[u]++;
            }
        }
    }

    if (edges_in_bb != X - 1) return false;

    int bb_c1 = 0, bb_c2 = 0;
    for (int u : backbone) {
        if (bb_deg[u] == 1) bb_c1++;
        else if (bb_deg[u] == 2) bb_c2++;
        else return false;
    }
    if (bb_c1 != 2 || bb_c2 != X - 2) return false;

    int visited_cnt = 0;
    V<bool> vis(N, false);
    auto dfs_bb = RecLambda([&](auto&& self, int u) -> void {
        vis[u] = true;
        visited_cnt++;
        for (int v : adj[u]) {
            if (d[v] == Y - 1 && !vis[v]) {
                self(v);
            }
        }
    });
    if (!backbone.empty()) dfs_bb(backbone[0]);
    if (visited_cnt != X) return false;

    return true;
}

bool solve_disco(int N, const V<V<int>>& adj) {
    V<int> comp(N, -1);
    V<V<int>> nodes(2);
    V<int> edges_cnt(2, 0);
    int c_idx = 0;
    rep(i, N) {
        if (comp[i] == -1) {
            if (c_idx >= 2) return false;
            V<int> q = {i};
            comp[i] = c_idx;
            nodes[c_idx].push_back(i);
            int head = 0;
            while (head < sz(q)) {
                int u = q[head++];
                for (int v : adj[u]) {
                    if (comp[v] == -1) {
                        comp[v] = c_idx;
                        nodes[c_idx].push_back(v);
                        q.push_back(v);
                    }
                }
            }
            c_idx++;
        }
    }
    if (c_idx != 2) return false;

    rep(k, 2) {
        for (int u : nodes[k]) for (int v : adj[u]) if (u < v) edges_cnt[k]++;
    }

    int uni = -1, tree = -1;
    if (edges_cnt[0] == sz(nodes[0]) && edges_cnt[1] == sz(nodes[1]) - 1) {
        uni = 0; tree = 1;
    } else if (edges_cnt[1] == sz(nodes[1]) && edges_cnt[0] == sz(nodes[0]) - 1) {
        uni = 1; tree = 0;
    } else {
        return false;
    }

    {
        int leaves = 0;
        for (int u : nodes[tree]) {
            if (sz(adj[u]) > 2) return false;
            if (sz(adj[u]) == 1) leaves++;
            if (sz(adj[u]) == 0) leaves++;
        }
        if (sz(nodes[tree]) > 1 && leaves != 2) return false;
        if (sz(nodes[tree]) == 1 && leaves != 1) return false;
    }

    V<int> deg(N);
    queue<int> q;
    for (int u : nodes[uni]) {
        deg[u] = sz(adj[u]);
        if (deg[u] == 1) q.push(u);
    }

    V<bool> on_cycle(N, true);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        on_cycle[u] = false;
        for (int v : adj[u]) {
            if (on_cycle[v]) {
                deg[v]--;
                if (deg[v] == 1) q.push(v);
            }
        }
    }

    V<int> cycle_nodes;
    for (int u : nodes[uni]) if (on_cycle[u]) cycle_nodes.push_back(u);

    int X = sz(cycle_nodes);
    if (X < 3) return false;
    if (N % X != 0) return false;
    int Y = N / X;

    for (int u : cycle_nodes) {
        int d_cyc = 0;
        for (int v : adj[u]) if (on_cycle[v]) d_cyc++;
        if (d_cyc != 2) return false;
    }

    V<int> tail_sizes;
    V<bool> visited(N, false);

    for (int root : cycle_nodes) {
        V<int> sub_nodes;
        sub_nodes.push_back(root);
        visited[root] = true;
        int ptr = 0;
        while (ptr < sz(sub_nodes)) {
            int u = sub_nodes[ptr++];
            for (int v : adj[u]) {
                if (!on_cycle[v] && !visited[v]) {
                    visited[v] = true;
                    sub_nodes.push_back(v);
                }
            }
        }

        bool is_simple_path = true;
        int sub_edges = 0;
        for (int u : sub_nodes) {
            int d = 0;
            for (int v : adj[u]) {
                if (!on_cycle[v]) {
                    d++;
                    if (u < v) sub_edges++;
                }
            }
            if (u == root) {
                if (d > 1) is_simple_path = false;
            } else {
                if (d > 2) is_simple_path = false;
            }
        }
        if (!is_simple_path) return false;
        if (sub_edges != sz(sub_nodes) - 1) return false;

        tail_sizes.push_back(sz(sub_nodes));
    }

    int short_tails = 0;
    int short_len = -1;
    for (int len : tail_sizes) {
        if (len == Y) continue;
        if (len < Y) {
            short_tails++;
            short_len = len;
        } else {
            return false;
        }
    }

    if (short_tails != 1) return false;
    if (short_len + sz(nodes[tree]) == Y) return true;

    return false;
}

void solve() {
    int N, M;
    in.read(N); in.read(M);
    V<V<int>> adj(N);
    V<int> deg(N, 0);
    rep(i, M) {
        int u, v; in.read(u); in.read(v);
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    if (M != N - 1) {
        out.print("No");
        return;
    }

    rep(i, N) if (deg[i] > 3) {
        out.print("No");
        return;
    }

    int comp_cnt = 0;
    V<bool> vis(N, false);
    rep(i, N) {
        if (!vis[i]) {
            comp_cnt++;
            if (comp_cnt > 2) {
                out.print("No");
                return;
            }
            V<int> q = {i};
            vis[i] = true;
            int head = 0;
            while(head < sz(q)){
                int u = q[head++];
                for(int v : adj[u]){
                    if(!vis[v]){
                        vis[v] = true;
                        q.push_back(v);
                    }
                }
            }
        }
    }

    bool ok = false;
    if (comp_cnt == 1) {
        ok = solve_tree(N, adj, deg);
    } else if (comp_cnt == 2) {
        ok = solve_disco(N, adj);
    } else {
        ok = false;
    }

    if (ok) out.print("Yes");
    else out.print("No");
}

int main() {
    solve();
    return 0;
}