結果

問題 No.3321 岩井星人グラフ-1
コンテスト
ユーザー のらら
提出日時 2025-10-29 18:33:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,232 bytes
コンパイル時間 3,614 ms
コンパイル使用メモリ 186,384 KB
実行使用メモリ 33,544 KB
最終ジャッジ日時 2025-10-29 18:33:57
合計ジャッジ時間 13,027 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48 WA * 2 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

//TLE
#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> chkcnt(4, 0);
    for(int i = 1; i <= N; i++) chkcnt[G[i].size()]++;
    if(chkcnt[0] != 0 || chkcnt[1] != x || chkcnt[2] != x * (y - 2) || chkcnt[3] != x) return false;

    vector<ll> 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] = 1;
            while(!que.empty()){
                ll pos = que.front(); que.pop();
                if(G[pos].size() == 3){
                    if(dist[pos] != y) return false;
                    continue;
                }
                for(auto to: G[pos]){
                    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;
                }
                if(chk[pos] == 1){
                    //探索済みならこの先に候補はない
                    break;
                }
                if(G[pos].size() < 3) 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);
    }
    for(int i = 0; i < (int)point.size(); i++){
        for(int j = i + 1; j < (int)point.size(); j++){
            bool isOK = true;
            for(auto to: G[point[i]]) if(to == point[j]) isOK = false;
            for(auto to: G[point[j]]) if(to == point[i]) isOK = false;
            if(isOK){
                G[point[i]].push_back(point[j]);
                G[point[j]].push_back(point[i]);
                if(check_iwai(x, y)) ret = true;
                G[point[i]].pop_back();
                G[point[j]].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]++;
    //cout << cnt[0] << " " << cnt[1] << " " << cnt[2] << " " << cnt[3] << endl;
    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