結果
| 問題 | No.3321 岩井星人グラフ-1 |
| コンテスト | |
| ユーザー |
 Neculapia
|
| 提出日時 | 2025-11-25 21:43:47 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,576 bytes |
| 記録 | |
| コンパイル時間 | 1,832 ms |
| コンパイル使用メモリ | 134,312 KB |
| 実行使用メモリ | 25,056 KB |
| 最終ジャッジ日時 | 2025-11-25 21:43:59 |
| 合計ジャッジ時間 | 11,727 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 78 WA * 11 |
ソースコード
/**
* 競技プログラミング解答コード
* 言語: C++23
*
* 解法アプローチ:
* 1. 岩井星人グラフの条件 (次数1と次数3がX個, 全ての葉から最寄りの次数3までの距離がL=Y-1) を満たすため、
* 追加する辺によって次数分布と距離関係を調整します。
* 2. 入力M != N-1 の場合は、最終的にN辺(1サイクル)を作る要件から即座にNoを出力します(孤立点対策含む)。
* ただし、孤立点がある場合は N頂点 N-1辺になりうるため、次数のGap解析で候補を絞ります。
* 3. 候補モード:
* - Mode 11: 葉同士を結ぶ (Gap=2, X不変)
* - Mode 22: 次数2同士を結ぶ (Gap=2, X+2)
* - Mode 12: 葉と次数2を結ぶ (Gap=2, X+1)
* - Mode 01/02: 孤立点処理 (Gap=0)
* 4. 距離条件の判定:
* - 既存の次数3頂点からの距離 `dist_old` をBFSで計算。
* - 条件を満たさない「悪い葉」を特定。
* - 「悪い葉」は、正しい距離Lの位置にある次数2頂点を次数3に昇格させることで救済する必要があります。
* この候補頂点は、葉から次数2のパスをL歩進んだ位置に一意に定まります(森構造のため)。
* - これにより候補探索を高速化し、全探索を回避します。
* 5. 最終確認 (`check_final`):
* - 候補ペアに対して実際に辺を追加し、BFSで全葉の距離条件を確認します。
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
const int INF = 1e9;
int N, M;
vector<vector<int>> adj;
vector<int> deg;
vector<int> dist_old;
vector<int> dist_to_leaf;
// 指定された葉から次数2の頂点のみを辿ってK歩進んだ頂点を返す
// パスが存在しない、分岐がある、次数条件を満たさない場合は-1
int get_node_at_dist_walk(int start, int K) {
if (K == 0) return start;
int curr = start;
int prev = -1;
for (int i = 0; i < K; ++i) {
int found = -1;
for (int nxt : adj[curr]) {
if (nxt != prev) {
found = nxt;
break;
}
}
if (found == -1) return -1;
// 途中経路は次数2でなければならない (分岐なし)
// 最終到達点は次数2でも3でも良いが、この関数の用途的に次数2を期待することが多い
// ただし、startが次数1であることを前提とする
// i < K-1 の間は次数2必須
if (deg[found] > 2 && i < K - 1) return -1;
prev = curr;
curr = found;
}
return curr;
}
// 最終チェック
bool check_final(int u, int v, int target_X, int target_L) {
// 既存の辺チェック
for (int nxt : adj[u]) if (nxt == v) return false;
deg[u]++; deg[v]++;
adj[u].push_back(v);
adj[v].push_back(u);
bool valid = true;
// 次数カウントとソース収集
int cn1 = 0;
vector<int> sources;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 1) cn1++;
else if (deg[i] == 3) sources.push_back(i);
else if (deg[i] > 3) valid = false;
}
if (valid && (cn1 != target_X || (int)sources.size() != target_X)) valid = false;
if (valid) {
static vector<int> d;
if ((int)d.size() != N + 1) d.resize(N + 1);
fill(d.begin(), d.end(), -1);
queue<int> q;
for (int s : sources) {
d[s] = 0;
q.push(s);
}
while (!q.empty()) {
int curr = q.front(); q.pop();
if (d[curr] >= target_L) continue; // 最短距離がLを超えても葉でなければ問題ないが、Lで打ち切り
for (int nxt : adj[curr]) {
if (d[nxt] == -1) {
d[nxt] = d[curr] + 1;
q.push(nxt);
}
}
}
for (int i = 1; i <= N; ++i) {
if (deg[i] == 1) {
if (d[i] != target_L) {
valid = false;
break;
}
}
}
}
// 復元
adj[u].pop_back();
adj[v].pop_back();
deg[u]--; deg[v]--;
return valid;
}
void bfs_dist(const vector<int>& starts, vector<int>& res) {
fill(res.begin(), res.end(), INF);
queue<int> q;
for (int u : starts) {
res[u] = 0;
q.push(u);
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (res[v] == INF) {
res[v] = res[u] + 1;
q.push(v);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M)) 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 (M > N) { cout << "No" << endl; return 0; } // 辺過多
// 次数超過チェック
for (int i = 1; i <= N; ++i) if (deg[i] > 3) { cout << "No" << endl; return 0; }
int n1 = 0, n3 = 0, n0 = 0;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 1) n1++;
else if (deg[i] == 3) n3++;
else if (deg[i] == 0) n0++;
}
int gap = n1 - n3;
vector<pair<string, int>> candidates;
if (n0 == 0) {
if (gap == 2) {
candidates.push_back({"11", n3});
candidates.push_back({"12", n3 + 1});
candidates.push_back({"22", n3 + 2});
}
} else if (n0 == 1) {
if (gap == 0) {
candidates.push_back({"01", n3});
candidates.push_back({"02", n3 + 1});
}
}
if (candidates.empty()) { cout << "No" << endl; return 0; }
// Precalc distances
vector<int> sources3, sources1;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 3) sources3.push_back(i);
if (deg[i] == 1) sources1.push_back(i);
}
dist_old.resize(N + 1);
dist_to_leaf.resize(N + 1);
bfs_dist(sources3, dist_old);
bfs_dist(sources1, dist_to_leaf);
for (auto [mode, X] : candidates) {
if (X <= 0 || N % X != 0) continue;
int Y = N / X;
if (Y < 2) continue;
int L = Y - 1;
if (mode == "11") {
vector<int> bad;
for (int l : sources1) if (dist_old[l] != L) bad.push_back(l);
if (bad.size() == 2) {
if (check_final(bad[0], bad[1], X, L)) { cout << "Yes" << endl; return 0; }
} else if (bad.empty()) {
if (sources1.size() >= 2) {
if (check_final(sources1[0], sources1[1], X, L)) { cout << "Yes" << endl; return 0; }
}
}
}
else if (mode == "22") {
bool possible = true;
vector<int> bad_leaves;
for (int l : sources1) {
if (dist_old[l] < L) { possible = false; break; }
if (dist_old[l] != L) bad_leaves.push_back(l);
}
if (!possible) continue;
set<int> targets;
bool target_possible = true;
for (int l : bad_leaves) {
int t = get_node_at_dist_walk(l, L);
if (t == -1) { target_possible = false; break; }
targets.insert(t);
}
if (!target_possible) continue;
if (targets.size() > 2) continue;
vector<int> target_list(targets.begin(), targets.end());
// 候補探索
// targetsに含まれる頂点は必須。残りは valid_deg2 から選ぶ。
// valid_deg2: deg=2 かつ dist_to_leaf >= L
auto is_valid_v = [&](int v) {
return deg[v] == 2 && dist_to_leaf[v] >= L;
};
if (target_list.size() == 2) {
int u = target_list[0];
int v = target_list[1];
if (is_valid_v(u) && is_valid_v(v)) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
}
} else if (target_list.size() == 1) {
int u = target_list[0];
if (is_valid_v(u)) {
// v を探索
int count = 0;
for (int v = 1; v <= N; ++v) {
if (v != u && is_valid_v(v)) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++count >= 50) break;
}
}
}
} else {
// targetなし (全ての葉が良い状態) -> 任意のvalidペア
vector<int> vs;
for (int v = 1; v <= N; ++v) if (is_valid_v(v)) vs.push_back(v);
int count = 0;
for (size_t i = 0; i < vs.size(); ++i) {
for (size_t j = i + 1; j < vs.size(); ++j) {
if (check_final(vs[i], vs[j], X, L)) { cout << "Yes" << endl; return 0; }
if (++count >= 50) goto next_mode;
}
}
}
}
else if (mode == "12") {
// dist_old < L な葉が2つ以上あれば救済不可 (uとして選べるのは1つだけ)
vector<int> too_close;
for (int l : sources1) if (dist_old[l] < L) too_close.push_back(l);
if (too_close.size() > 1) continue;
vector<int> potential_us;
if (too_close.size() == 1) potential_us.push_back(too_close[0]);
else {
for (int l : sources1) if (dist_old[l] != L) potential_us.push_back(l);
if (potential_us.size() > 50) potential_us.resize(50);
// 正常な葉も少し試す
int cnt = 0;
for (int l : sources1) {
if (dist_old[l] == L) {
potential_us.push_back(l);
if (++cnt >= 10) break;
}
}
}
for (int u : potential_us) {
// u を取り除いたとき、他の悪い葉を救う v が必要
// needed: dist_old > L or INF (dist_old < L はありえない、上でフィルタ済)
vector<int> needed;
for (int l : sources1) if (l != u && (dist_old[l] > L || dist_old[l] == INF)) needed.push_back(l);
int req_v = -1;
bool possible_u = true;
for (int l : needed) {
// u 経由で解決可能か? (dist(l, u) == L - 1)
int t_u = get_node_at_dist_walk(l, L - 1);
if (t_u == u) continue; // u経由でOK
// v 経由で解決必須 (dist(l, v) == L, v is ancestor)
int t_v = get_node_at_dist_walk(l, L);
if (t_v == -1) { possible_u = false; break; }
if (req_v == -1) req_v = t_v;
else if (req_v != t_v) { possible_u = false; break; }
}
if (!possible_u) continue;
if (req_v != -1) {
int v = req_v;
if (v != u && deg[v] == 2) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
}
} else {
// 制約なし。任意のvalidなv
int count = 0;
for (int v = 1; v <= N; ++v) {
if (v != u && deg[v] == 2) {
// ヒューリスティック: dist_to_leaf >= L のものを優先
// ただし u が close な場合もあるので厳密には check_final 任せ
if (dist_to_leaf[v] >= L) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++count >= 50) break;
}
}
}
// dist_to_leaf < L のものも少し試すべき？
// u が唯一近い葉ならばOKなケースがあるため
if (count < 10) {
for (int v = 1; v <= N; ++v) {
if (v != u && deg[v] == 2 && dist_to_leaf[v] < L) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++count >= 60) break;
}
}
}
}
}
}
else if (mode == "01") {
int iso = -1;
for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
if(iso != -1) {
// v は dist_old == L-1 である葉
for (int v : sources1) {
if (dist_old[v] == L - 1) {
bool ok = true;
for (int l : sources1) if (l != v && dist_old[l] != L) { ok = false; break; }
if (ok && check_final(iso, v, X, L)) { cout << "Yes" << endl; return 0; }
}
}
}
}
else if (mode == "02") {
int iso = -1;
for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
if(iso != -1 && L == 1) {
bool ok = true;
for (int l : sources1) if (dist_old[l] != 1) { ok = false; break; }
if (ok) {
int count = 0;
for (int v = 1; v <= N; ++v) {
if (deg[v] == 2) {
if (check_final(iso, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++count >= 50) break;
}
}
}
}
}
next_mode:;
}
cout << "No" << endl;
return 0;
}