結果
| 問題 | No.3321 岩井星人グラフ-1 |
| コンテスト | |
| ユーザー |
 Neculapia
|
| 提出日時 | 2025-11-25 21:06:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,267 bytes |
| 記録 | |
| コンパイル時間 | 6,479 ms |
| コンパイル使用メモリ | 153,104 KB |
| 実行使用メモリ | 37,372 KB |
| 最終ジャッジ日時 | 2025-11-25 21:07:45 |
| 合計ジャッジ時間 | 11,217 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 68 WA * 21 |
ソースコード
/**
* 解法アプローチ:
* 1. 入力グラフは N 頂点 M 辺で、1辺追加して岩井星人グラフ（N頂点 N辺、次数条件、距離条件）を作る必要がある。
* 2. 最終的に N 辺になるため、入力は M = N - 1（森）であることが必要条件。
* 3. 岩井星人グラフの条件:
* - 次数1の頂点数 = 次数3の頂点数 = X
* - 全ての次数1頂点から、最も近い次数3頂点への距離が Y-1 (L) である。
* 4. 辺追加による次数変化と X の整合性を確認するため、Gap = Count(Deg1) - Count(Deg3) に着目する。
* - Gap = 2 の場合 (通常の木構造など):
* - Mode 11: 葉と葉を結ぶ (X = C3)。
* - Mode 12: 葉と次数2を結ぶ (X = C3 + 1)。
* - Mode 22: 次数2同士を結ぶ (X = C3 + 2)。
* - Gap = 0 かつ 孤立点ありの場合:
* - Mode 01, 02 を試す。
* 5. 各モードについて、距離条件 L を満たす候補ペアを探索する。
* - 距離条件を満たさない「悪い葉」を特定し、それらを被覆できる候補頂点を集合交差や探索で絞り込む。
* - N が最大 3x10^5 なので、候補全探索は不可。必要条件（距離 L、葉に近づきすぎない等）で候補を絞り、
* 最終確認 (check_final) で実際にBFSを行い判定する。
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
// 定数・グローバル変数
const int INF = 1e9;
int N, M;
vector<vector<int>> adj;
vector<int> deg;
// 距離計算用 (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);
}
}
}
}
// 2点間距離 (BFS)
int get_single_dist(int s, int t) {
if (s == t) return 0;
queue<pair<int, int>> q;
q.push({s, 0});
vector<int> visited_dist(N + 1, -1);
visited_dist[s] = 0;
while (!q.empty()) {
auto [u, d] = q.front(); q.pop();
if (u == t) return d;
if (d >= visited_dist[s] + N) continue; // Safety break, though BFS finds shortest
for (int v : adj[u]) {
if (visited_dist[v] == -1) {
visited_dist[v] = d + 1;
q.push({v, d + 1});
}
}
}
return INF;
}
// 最終チェック: 辺 (u, v) を追加して条件を満たすか
bool check_final(int u, int v, int target_X, int target_L) {
// 辺追加
deg[u]++; deg[v]++;
adj[u].push_back(v);
adj[v].push_back(u);
// 次数3以上の頂点を始点にBFS
vector<int> sources;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 3) sources.push_back(i);
else if (deg[i] > 3) { // 次数超過チェック
deg[u]--; deg[v]--; adj[u].pop_back(); adj[v].pop_back();
return false;
}
}
// Xの一致確認
int n1 = 0;
for (int i = 1; i <= N; ++i) if (deg[i] == 1) n1++;
if (n1 != target_X || (int)sources.size() != target_X) {
deg[u]--; deg[v]--; adj[u].pop_back(); adj[v].pop_back();
return false;
}
vector<int> d(N + 1, -1);
queue<int> q;
for (int s : sources) {
d[s] = 0;
q.push(s);
}
bool valid = true;
while (!q.empty()) {
int curr = q.front(); q.pop();
// Lより深い探索は判定に不要だが、L未満の葉を見つけるために必要
// ただし最適化として L+1 程度で打ち切る手もあるが、正確性重視
if (d[curr] > target_L) continue;
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;
}
}
}
// 戻す
deg[u]--; deg[v]--;
adj[u].pop_back(); adj[v].pop_back();
return valid;
}
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]++;
}
// 次数超過チェック
for (int d : deg) if (d > 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; }
// 前計算: 既存の次数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);
// 前計算: 最寄りの葉までの距離
vector<int> leaves;
for (int i = 1; i <= N; ++i) if (deg[i] == 1) leaves.push_back(i);
vector<int> dist_to_leaf(N + 1);
get_dists(leaves, 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 : leaves) 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 (leaves.size() >= 2) {
if (check_final(leaves[0], leaves[1], X, L)) { cout << "Yes" << endl; return 0; }
}
}
}
else if (mode == "22") {
// 条件: dist_old >= L であること（近すぎる葉は救えない）
bool possible = true;
for (int l : leaves) if (dist_old[l] < L) { possible = false; break; }
if (!possible) continue;
vector<int> bad_leaves;
for (int l : leaves) if (dist_old[l] != L) bad_leaves.push_back(l);
// 悪い葉をカバーできる候補頂点集合を計算
vector<set<int>> cover_sets;
for (int l : bad_leaves) {
set<int> s;
// BFSで距離Lの次数2頂点を探す
queue<pair<int, int>> q;
q.push({l, 0});
set<int> vis; vis.insert(l);
while (!q.empty()) {
auto [u, d] = q.front(); q.pop();
if (d == L) {
if (deg[u] == 2) s.insert(u);
continue;
}
if (d < L) {
for (int v : adj[u]) {
if (vis.find(v) == vis.end()) {
vis.insert(v);
q.push({v, d + 1});
}
}
}
}
if (s.empty()) { possible = false; break; }
cover_sets.push_back(s);
}
if (!possible) continue;
// 有効な次数2頂点 (他の葉に近すぎない)
vector<int> valid_deg2;
for (int i = 1; i <= N; ++i) {
if (deg[i] == 2 && dist_to_leaf[i] >= L) valid_deg2.push_back(i);
}
set<int> valid_set(valid_deg2.begin(), valid_deg2.end());
// cover_sets を valid_set でフィルタリング
vector<set<int>> filtered_sets;
for (const auto& s : cover_sets) {
set<int> inter;
for (int x : s) if (valid_set.count(x)) inter.insert(x);
if (inter.empty()) { possible = false; break; }
filtered_sets.push_back(inter);
}
if (!possible) continue;
if (filtered_sets.empty()) {
if (valid_deg2.size() >= 2) {
if (check_final(valid_deg2[0], valid_deg2[1], X, L)) { cout << "Yes" << endl; return 0; }
}
} else {
sort(filtered_sets.begin(), filtered_sets.end(), [](const set<int>& a, const set<int>& b){
return a.size() < b.size();
});
// Set Coverの探索 (u を最小集合から選ぶ)
int limit = 0;
for (int u : filtered_sets[0]) {
if (++limit > 50) break;
vector<int> uncovered_idx;
for (size_t i = 0; i < filtered_sets.size(); ++i) {
if (filtered_sets[i].find(u) == filtered_sets[i].end()) uncovered_idx.push_back(i);
}
if (uncovered_idx.empty()) {
for (int v : valid_deg2) {
if (v != u) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
break;
}
}
} else {
set<int> cand_v = filtered_sets[uncovered_idx[0]];
for (size_t k = 1; k < uncovered_idx.size(); ++k) {
set<int> next_s;
set_intersection(cand_v.begin(), cand_v.end(),
filtered_sets[uncovered_idx[k]].begin(), filtered_sets[uncovered_idx[k]].end(),
inserter(next_s, next_s.begin()));
cand_v = next_s;
if (cand_v.empty()) break;
}
int v_limit = 0;
for (int v : cand_v) {
if (++v_limit > 50) break;
if (v != u) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
}
}
}
}
}
}
else if (mode == "12") {
// 条件: dist_old < L である葉が2つ以上あったら無理
vector<int> too_close;
for (int l : leaves) 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 : leaves) if (dist_old[l] > L || dist_old[l] == INF) potential_us.push_back(l);
if (potential_us.size() > 50) potential_us.resize(50);
// 距離整合の葉も少し試す
int cnt = 0;
for (int l : leaves) {
if (dist_old[l] == L) {
potential_us.push_back(l);
if (++cnt >= 10) break;
}
}
}
for (int u : potential_us) {
// uを葉から除外した状況で、v (deg 2) が他のすべての葉に対して適切か確認
// needed: v によってカバーされるべき葉 (dist_old > L or INF)
vector<int> needed;
for (int l : leaves) if (l != u && (dist_old[l] > L || dist_old[l] == INF)) needed.push_back(l);
if (needed.empty()) {
// v は他の全ての葉から距離 L 以上離れていれば良い
int v_tries = 0;
for (int v = 1; v <= N; ++v) {
if (deg[v] == 2) {
// dist_to_leaf[v] は u も含む距離なので、u が近い分には許容される
// dist_to_leaf[v] >= L なら安全
// dist_to_leaf[v] < L の場合、その近さが u によるものならOK
if (dist_to_leaf[v] >= L) {
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++v_tries > 50) break;
} else {
// 近い葉が u だけか確認
int d_uv = get_single_dist(u, v);
if (d_uv == dist_to_leaf[v]) {
// 可能性あり
if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if (++v_tries > 50) break;
}
}
}
}
} else {
// needed の共通部分を探す
int l0 = needed[0];
set<int> cands;
// BFS from l0
queue<pair<int,int>> q; q.push({l0, 0});
set<int> vis; vis.insert(l0);
while(!q.empty()){
auto [c, d] = q.front(); q.pop();
if(d == L){
if(deg[c] == 2) cands.insert(c);
continue;
}
if(d < L){
for(int nxt : adj[c]){
if(vis.find(nxt) == vis.end()){
vis.insert(nxt);
q.push({nxt, d+1});
}
}
}
}
int v_tries = 0;
for(int v : cands) {
if(v == u) continue;
if(check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
if(++v_tries > 50) 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) continue;
for(int l : leaves) {
if(dist_old[l] == L - 1) {
if(check_final(iso, l, 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) continue;
bool ok = true;
for(int l : leaves) if(dist_old[l] != 1) { ok = false; break; }
if(ok) {
int tries = 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(++tries > 10) break;
}
}
}
}
}
cout << "No" << endl;
return 0;
}