結果

問題 No.3321 岩井星人グラフ-1
コンテスト
ユーザー のらら
提出日時 2025-07-10 14:09:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,896 bytes
コンパイル時間 2,851 ms
コンパイル使用メモリ 185,920 KB
実行使用メモリ 24,320 KB
最終ジャッジ日時 2025-07-13 14:01:30
合計ジャッジ時間 5,480 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

//時間計測用
#include <iostream>
#include <algorithm>
#include <atcoder/all>
#include <set>
#include <queue>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll N, M, cnt[4];
vector<ll> G[300009];

//岩井星人グラフかどうか判定
bool check_iwai(ll x, ll y){
    ll line = 0;
    for(int i = 1; i <= N; i++){
        line += G[i].size();
    }
    if(line % 2 != 0) return false;
    line /= 2;
    if(!(N == line && N == x * y)) return false;

    vector<ll> cnt(4, 0);
    for(int i = 1; i <= N; i++) cnt[G[i].size()]++;
    if(cnt[0] != 0 || cnt[1] != x || cnt[2] != x * (y - 2) || cnt[3] != x) return false;

    vector<bool> dist(N + 1, -1);
    for(int i = 1; i <= N; i++){
        if(dist[i] != -1) continue;
        if(G[i].size() == 1){
            queue<ll> que;
            que.push(i);
            dist[i] = 0;
            while(!que.empty()){
                ll pos = que.front(); que.pop();
                for(auto to: G[pos]){
                    if(G[to].size() == 3){
                        if(dist[to] != y) return false;
                    }
                    if(dist[to] == -1){
                        dist[to] = dist[pos] + 1;
                        que.push(to);
                    }
                }
            }
        }
    }
    return true;
}

//腕の本数x,腕の長さyの岩井星人グラフにできるか
bool calc(ll x, ll y){
    bool ret = false;
    vector<ll> point;
    vector<ll> chk(N + 1, 0);
    for(int i = 1; i <= N; i++){
        if(chk[i]) continue;
        if(G[i].size() == 0){
            point.push_back(i);
            chk[i] = 1;
            continue;
        }
        if(G[i].size() == 1){
            int pos = i, pre = -1;
            int num = 1;
            chk[pos] = 1;
            while(1){
                for(auto to: G[pos]){
                    if(to == pre) continue;
                    pre = pos;
                    pos = to;
                    break;
                }
                chk[pos] = 1;
                num++;
                if(num < y){
                    if(G[pos].size() == 1){
                        //パスグラフだった
                        point.push_back(pos);
                        break;
                    }
                    if(G[pos].size() == 3){
                        //腕の長さが足りない
                        point.push_back(i);
                        break;
                    }
                }
                if(num == y){
                    if(G[pos].size() == 2){
                        point.push_back(pos);
                    }
                    break;
                }
            }
        }
    }
    for(int i = 1; i <= N; i++){
        if(chk[i] == 0 && G[i].size() == 2) point.push_back(i);
    }
    point.erase(unique(point.begin(), point.end()), point.end());
    if(point.size() == 2){
        bool isOK = true;
        for(auto to: G[point[0]]) if(to == point[1]) isOK = false;
        for(auto to: G[point[1]]) if(to == point[0]) isOK = false;
        if(isOK){
            G[point[0]].push_back(point[1]);
            G[point[1]].push_back(point[0]);
            if(check_iwai(x, y)) ret = true;
            G[point[0]].pop_back();
            G[point[1]].pop_back();
        }
    }
    return ret;
}

//次数p1,p2の頂点の1つをp1+1,p2+1にした場合を考える
bool check_add_line(ll p1, ll p2){
    bool ret = false;
    cnt[p1]--; cnt[p1 + 1]++; cnt[p2]--; cnt[p2 + 1]++;
    if(cnt[1] == cnt[3] && cnt[1] >= 3 && gcd(cnt[1], cnt[2]) == cnt[1]){
        ll len = cnt[2] / cnt[1] + 2; //腕の長さ
        ret = calc(cnt[1], len);
    }
    cnt[p1]++; cnt[p1 + 1]--; cnt[p2]++; cnt[p2 + 1]--;
    return ret;
}

int main(){
    cin >> N >> M;
    if(N - 1 != M){
        //XY頂点XY-1辺である条件を満たさない
        cout << "No" << endl;
        return 0;
    }
    for(int i = 0; i < M; i++){
        ll a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i = 1; i <= N; i++){
        if(G[i].size() >= 4){
            //次数が4以上の頂点を含んではいけない
            cout << "No" << endl;
            return 0;
        }
        cnt[G[i].size()]++;
    }

    bool isOK = false;
    if(cnt[0] == 1){
        //0→1,1→2(延長パターン(Y>3))
        isOK |= check_add_line(0, 1);

        //0→1,2→3(腕を増やすパターン(Y=2))
        isOK |= check_add_line(0, 2);
    }
    if(cnt[0] == 0){
        //1→2,1→2(連結パターン(Y>4))
        isOK |= check_add_line(1, 1);

        //1→2,2→3(腕を増やすパターン(Y>2))
        isOK |= check_add_line(1, 2);

        //2→3,2→3(ループを増やすパターン)
        isOK |= check_add_line(2, 2);
    }
    if(isOK) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}
0