結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー GOTKAKO
提出日時 2026-07-10 22:25:51
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 3,379 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,495 ms
コンパイル使用メモリ 230,452 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-10 22:25:58
合計ジャッジ時間 6,089 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

vector<int> BFS(vector<vector<int>> &Graph,int start){
    int N = Graph.size();
    vector<int> ret(N,-1);
    queue<int> Q;
    ret.at(start) = 0,Q.push(start);
    while(Q.size()){
        int pos = Q.front(); Q.pop();
        for(auto to : Graph.at(pos)){
            if(ret.at(to) != -1) continue;
            ret.at(to) = ret.at(pos)+1;
            Q.push(to);
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    
    int N,M,K; cin >> N >> M >> K;

    auto no = [&]() -> void {
        vector<pair<int,int>> Es;
        for(int i=0; i<N; i++) for(int k=i+1; k<N; k++) Es.push_back({i,k});
        int n = Es.size(),n2 = 1<<n;
        for(int i=0; i<n2; i++){
            if(__popcount((unsigned int)i) != M) continue;
            vector<vector<int>> Graph(N);
            for(int k=0; k<n; k++) if(!(i&(1<<k))){
                auto [u,v] = Es.at(k);
                Graph.at(u).push_back(v);
                Graph.at(v).push_back(u);
            }
            
            if(BFS(Graph,0).at(N-1) == K){
                cout << "Wrong" << endl;
                cout << N << " " << M << " " << K << endl;
                exit(0);
            }
        }


        cout << "No\n";
    };

    int edge = N*(N-1)/2;
    vector<pair<int,int>> del;
    if(K == 1){
        if(M == edge) no();
        else{
            for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){
                if(i == 0 && k == N-1) continue;
                if(del.size() != M) del.push_back({i,k});
            }
            if(del.size() != M) cout << "No\n"; 
            else{
                cout << "Yes\n";
                vector<vector<bool>> G(N,vector<bool>(N,true));
                vector<vector<int>> Graph(N);
                for(auto [u,v] : del) cout << u+1 << " " << v+1 << "\n",G.at(u).at(v) = false;
                for(int i=0; i<N; i++) for(int k=i+1; k<N; k++) if(G.at(i).at(k)) Graph.at(i).push_back(k),Graph.at(k).push_back(i);
                
                auto dist = BFS(Graph,0);
                if(dist.at(N-1) != K){
                    cout << "Wrong" << endl;
                    cout << N << " " << del.size() << " " << K << endl;
                    return 0;
                }

                
            }
        }
    }
    else{

        for(int i=0; i<K-2; i++) for(int k=i+2; k<N; k++) del.push_back({i,k});
        del.push_back({K-2,N-1});
        for(int i=K-2; i<N; i++) for(int k=i+1; k<N; k++){
            if(i == K-2 && k == N-1) continue;
            if(i == K-2 && k == K-1) continue;
            if(i == K-1 && k == N-1) continue;
            if(del.size() < M) del.push_back({i,k});
        }
        if(del.size() != M) no();
        else{

            cout << "Yes\n";
            vector<vector<bool>> G(N,vector<bool>(N,true));
            vector<vector<int>> Graph(N);
            for(auto [u,v] : del) cout << u+1 << " " << v+1 << "\n",G.at(u).at(v) = false;
            for(int i=0; i<N; i++) for(int k=i+1; k<N; k++) if(G.at(i).at(k)) Graph.at(i).push_back(k),Graph.at(k).push_back(i);

            auto dist = BFS(Graph,0);
            if(dist.at(N-1) != K){
                cout << "Wrong" << endl;
                cout << N << " " << del.size() << " " << K << endl;
                return 0;
            }
        }

    }

}
0