結果
| 問題 | No.3321 岩井星人グラフ-1 |
| コンテスト | |
| ユーザー |
 Neculapia
|
| 提出日時 | 2025-11-25 21:01:17 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,273 bytes |
| 記録 | |
| コンパイル時間 | 2,305 ms |
| コンパイル使用メモリ | 153,140 KB |
| 実行使用メモリ | 29,032 KB |
| 最終ジャッジ日時 | 2025-11-25 21:01:28 |
| 合計ジャッジ時間 | 10,040 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 70 WA * 19 |
ソースコード
/**
* 競技プログラミング解答コード
* 言語: C++23
*
* 解法アプローチ:
* 1. 岩井星人グラフは、頂点数 XY、辺数 XY を持ち、次数1がX個、次数2がX(Y-2)個、次数3がX個です。
* また、すべての次数1の頂点から最も近い次数3の頂点までの距離が Y-1 である必要があります。
* 入力として与えられるグラフは N 頂点 M 辺で、辺を1本追加してこの条件を満たす必要があります。
* したがって、追加後のグラフは N 辺を持つため、M = N - 1（森または木）でなければなりません。
*
* 2. 辺を追加することで変化する次数パターンは限られます。
* - 次数0(孤立点)がある場合、ない場合で分類できます。
* - 次数4以上が存在してはいけません。
* - 追加する辺 (u, v) の次数ペアによって、次数1, 2, 3 の頂点数の増減が決まります。
* - これにより、最終的な X と Y の候補が決まり、必要な距離 L = Y - 1 が定まります。
*
* 3. 候補となる L に対して、既存の次数3頂点からの距離を確認し、条件を満たさない「悪い葉」や
* 新たに次数3となるべき「カバー候補」を特定します。
* - ケース (1,1): 次数1同士を結ぶ。2つの葉が消える。残りの葉の距離条件を確認。
* - ケース (2,2): 次数2同士を結び、新しい次数3を2つ作る。すべての葉が距離 L で次数3に到達できるようにするSet Cover問題として処理。
* - ケース (0,1), (0,2): 孤立点の処理。
*
* 4. 候補ペアが見つかった場合、実際に辺を追加してBFSを行い、全条件（次数、距離）を満たすか確認します。
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <iterator>
#include <map>
using namespace std;
// グローバル変数
int N, M;
vector<vector<int>> adj;
vector<int> deg;
const int INF = 1e9;
// 複数始点からの最短距離を計算 (BFS)
void get_dists(const vector<int>& sources, vector<int>& d) {
fill(d.begin(), d.end(), INF);
queue<int> q;
for (int u : sources) {
d[u] = 0;
q.push(u);
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (d[v] == INF) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
}
// 指定された頂点対 (u, v) を追加したときに岩井星人グラフになるか判定
bool check_pair(int u, int v, int target_X) {
// 多重辺チェック
for (int neighbor : adj[u]) if (neighbor == v) return false;
// グラフ変更
deg[u]++; deg[v]++;
// 次数チェック
if (deg[u] > 3 || deg[v] > 3) { deg[u]--; deg[v]--; return false; }
int n1 = 0, n3 = 0;
vector<int> deg3_nodes;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 1) n1++;
else if (deg[i] == 3) {
n3++;
deg3_nodes.push_back(i);
} else if (deg[i] > 3) {
deg[u]--; deg[v]--; return false;
}
}
// Xの一致確認
if (n1 != n3 || n1 != target_X) { deg[u]--; deg[v]--; return false; }
if (target_X == 0 || N % target_X != 0) { deg[u]--; deg[v]--; return false; }
int Y = N / target_X;
if (Y < 2) { deg[u]--; deg[v]--; return false; }
int L = Y - 1;
// 距離条件の確認 (次数3の頂点群からのBFS)
static vector<int> d;
if (d.size() != N + 1) d.resize(N + 1);
fill(d.begin(), d.end(), -1);
queue<int> q;
for (int x : deg3_nodes) {
d[x] = 0;
q.push(x);
}
// 辺 (u, v) を考慮したBFS
while (!q.empty()) {
int curr = q.front(); q.pop();
if (d[curr] >= L) continue; // Lより遠くを探索する必要はない（葉までの距離がLかどうかが重要）
auto push = [&](int nxt) {
if (d[nxt] == -1) {
d[nxt] = d[curr] + 1;
q.push(nxt);
}
};
for (int nxt : adj[curr]) push(nxt);
if (curr == u) push(v);
if (curr == v) push(u);
}
bool ok = true;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 1) {
if (d[i] != L) { ok = false; break; }
}
}
// 変更を戻す
deg[u]--; deg[v]--;
return ok;
}
int main() {
// 高速化
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M)) return 0;
// 岩井星人グラフは辺数 N を持つため、追加前は N-1 でなければならない（森）
if (M != N - 1) { cout << "No" << endl; return 0; }
adj.resize(N + 1);
deg.resize(N + 1, 0);
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++; deg[v]++;
}
// 既定の次数超過チェック
if (any_of(deg.begin(), deg.end(), [](int d){ return d > 3; })) {
cout << "No" << endl; return 0;
}
int cnt[5] = {0};
for (int i = 1; i <= N; ++i) cnt[deg[i]]++;
int c0 = cnt[0];
int c3 = cnt[3];
// 既存の次数3頂点からの距離を計算
vector<int> dist_old(N + 1);
vector<int> sources;
for (int i = 1; i <= N; ++i) if (deg[i] == 3) sources.push_back(i);
get_dists(sources, dist_old);
// 候補となる操作（追加する辺のタイプ）と目標X
vector<pair<string, int>> candidates;
if (c0 == 0) {
// 全域をカバー済み。次数1または次数2同士を結ぶ
if (c3 > 0) candidates.push_back({"11", c3}); // 葉同士を結ぶ (葉が2つ減る, X不変) -> 実は X = C1 - 2 = C3 (元々C1=C3+2)
candidates.push_back({"22", c3 + 2}); // 次数2同士を結ぶ (Xが2つ増える)
} else if (c0 == 1) {
// 孤立点が1つ
if (c3 > 0) candidates.push_back({"01", c3}); // 孤立点と葉を結ぶ
candidates.push_back({"02", c3 + 1}); // 孤立点と次数2を結ぶ
}
// c0 >= 2 は岩井星人グラフ（連結または特定構造）に不可（サンプル2のようなケースでも成分ごとには成立必要）
for (auto [mode, X] : candidates) {
if (X <= 0 || N % X != 0) continue;
int Y = N / X;
if (Y < 2) continue;
int L = Y - 1;
vector<int> leaves;
for (int i = 1; i <= N; ++i) if (deg[i] == 1) leaves.push_back(i);
if (mode == "11") {
// 現在の葉の中で距離Lを満たさないものをリストアップ
vector<int> bad;
for (int l : leaves) {
if (dist_old[l] != L) bad.push_back(l);
}
// 悪い葉が2つなら、それらを結んで解消できるか試す
if (bad.size() == 2) {
if (check_pair(bad[0], bad[1], X)) { cout << "Yes" << endl; return 0; }
} else if (bad.empty() && leaves.size() >= 2) {
// 全て良いなら、任意の葉ペアで試す（最初のペアで十分）
if (check_pair(leaves[0], leaves[1], X)) { cout << "Yes" << endl; return 0; }
}
}
else if (mode == "22") {
// 次数2同士を結んで新しい次数3を2つ作る
// 既存の次数3から距離L未満の葉があると、距離を伸ばせないので不可
// 距離Lより遠い葉は、新しい次数3によって距離Lでカバーされなければならない
vector<set<int>> cover_sets;
bool possible = true;
for (int l : leaves) {
if (dist_old[l] < L) { possible = false; break; }
if (dist_old[l] == L) continue; // 既存でカバー済み
// 新しいカバー候補を探す (葉から距離Lの地点)
set<int> s;
queue<pair<int,int>> q;
q.push({l, 0});
set<int> visited; visited.insert(l);
while(!q.empty()){
auto [u, d] = q.front(); q.pop();
if (d == L) {
if (deg[u] == 2) s.insert(u);
continue;
}
for (int v : adj[u]) {
if (visited.find(v) == visited.end()) {
visited.insert(v);
q.push({v, d+1});
}
}
}
if (s.empty()) { possible = false; break; }
cover_sets.push_back(s);
}
if (!possible) continue;
if (cover_sets.empty()) {
// 全ての葉が既存の次数3でカバーされている場合
// 距離条件を壊さない（葉に近づきすぎない）任意の次数2ペアを探す
// 葉からの距離が L 以上の次数2頂点が候補
vector<int> d_leaf(N + 1, INF);
queue<int> q;
for(int l : leaves) { d_leaf[l] = 0; q.push(l); }
while(!q.empty()){
int u = q.front(); q.pop();
for(int v : adj[u]){
if(d_leaf[v] == INF){
d_leaf[v] = d_leaf[u] + 1;
q.push(v);
}
}
}
vector<int> valid_u;
for(int i=1; i<=N; ++i) if(deg[i]==2 && d_leaf[i] >= L) valid_u.push_back(i);
// 候補からいくつか試す
int tries = 0;
for(size_t i=0; i<valid_u.size() && tries < 50; ++i){
for(size_t j=i+1; j<valid_u.size() && tries < 50; ++j){
tries++;
if(check_pair(valid_u[i], valid_u[j], X)) { cout << "Yes" << endl; return 0; }
}
}
} else {
// カバーが必要な葉がある場合
// 最小の候補集合を持つ葉に着目し、その候補のいずれかを採用する必要がある
sort(cover_sets.begin(), cover_sets.end(), [](const set<int>& a, const set<int>& b){ return a.size() < b.size(); });
vector<int> S_min(cover_sets[0].begin(), cover_sets[0].end());
for(int u : S_min) {
// u を選んだと仮定し、u でカバーできない残りの集合を特定
vector<int> uncovered_idx;
for(size_t i=0; i<cover_sets.size(); ++i) {
if(cover_sets[i].find(u) == cover_sets[i].end()) uncovered_idx.push_back(i);
}
if(uncovered_idx.empty()) {
// u だけで全てカバーできる場合、v は任意のvalidな頂点で良い
// ヒューリスティックに探す
for(int v=1; v<=N; ++v){
if(deg[v]==2 && v!=u){
if(check_pair(u, v, X)) { cout << "Yes" << endl; return 0; }
if(v > 200 && v % 50 == 0) break;
}
}
} else {
// 残りをカバーできる v を探す (共通部分集合)
set<int> intersect = cover_sets[uncovered_idx[0]];
for(size_t k=1; k<uncovered_idx.size(); ++k) {
set<int> next_s;
set_intersection(intersect.begin(), intersect.end(),
cover_sets[uncovered_idx[k]].begin(), cover_sets[uncovered_idx[k]].end(),
inserter(next_s, next_s.begin()));
intersect = next_s;
if(intersect.empty()) break;
}
for(int v : intersect) {
if(v != u) {
if(check_pair(u, v, X)) { cout << "Yes" << endl; return 0; }
}
}
}
}
}
}
else if (mode == "01") {
// 孤立点と葉を結ぶ
int iso = -1;
for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
if(iso == -1) continue;
// 接続先の葉 v は、現在の距離が L-1 である必要がある（接続後、孤立点が新しい葉となり距離Lになる）
vector<int> cands;
for(int l : leaves) if(dist_old[l] == L-1) cands.push_back(l);
for(int v : cands) {
// v 以外の葉は距離 L でなければならない
bool ok = true;
for(int l : leaves) {
if(l != v && dist_old[l] != L) { ok = false; break; }
}
if(ok) {
if(check_pair(iso, v, X)) { cout << "Yes" << endl; return 0; }
}
}
}
else if (mode == "02") {
// 孤立点と次数2を結ぶ (L=1 のケース)
bool ok = true;
for(int l : leaves) if(dist_old[l] != 1) { ok = false; break; }
if(ok) {
int iso = -1;
for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
// 任意の次数2で試す
for(int i=1; i<=N; ++i) {
if(deg[i]==2) {
if(check_pair(iso, i, X)) { cout << "Yes" << endl; return 0; }
break;
}
}
}
}
}
cout << "No" << endl;
return 0;
}