結果
| 問題 | No.3321 岩井星人グラフ-1 |
| コンテスト | |
| ユーザー |
 Neculapia
|
| 提出日時 | 2025-11-25 10:15:15 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,125 bytes |
| 記録 | |
| コンパイル時間 | 5,357 ms |
| コンパイル使用メモリ | 375,592 KB |
| 実行使用メモリ | 28,744 KB |
| 最終ジャッジ日時 | 2025-11-25 10:15:29 |
| 合計ジャッジ時間 | 13,293 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 53 TLE * 1 -- * 35 |
コンパイルメッセージ
main.cpp: In member function ‘void Printer::flush()’:
main.cpp:123:20: warning: ignoring return value of ‘ssize_t write(int, const void*, size_t)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
123 | ::write(fd, buf.data(), idx);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘void solve()’:
main.cpp:181:39: warning: ‘v’ may be used uninitialized [-Wmaybe-uninitialized]
181 | int u, v; in.read(u, v); --u; --v;
| ^~~
main.cpp:181:16: note: ‘v’ was declared here
181 | int u, v; in.read(u, v); --u; --v;
| ^
main.cpp:159:37: warning: ‘M’ may be used uninitialized [-Wmaybe-uninitialized]
159 | #define rep(i, n) for (i32 i = 0; i < (i32)(n); ++i)
| ^
main.cpp:180:5: note: in expansion of macro ‘rep’
180 | rep(i, M) {
| ^~~
main.cpp:176:12: note: ‘M’ was declared here
176 | int N, M;
| ^
ソースコード
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <unistd.h>
#include <ext/pb_ds/assoc_container.hpp>
#ifdef ATCODER
#include <atcoder/all>
#endif
using namespace std;
using namespace __gnu_pbds;
#ifdef ATCODER
using namespace atcoder;
#endif
using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
using pii = pair<i32, i32>;
using pll = pair<i64, i64>;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr int INF32 = (1 << 30);
constexpr i64 INF64 = (i64(1) << 60);
struct Scanner {
static constexpr size_t BUFSIZE = 1 << 20;
int fd;
size_t idx;
size_t size;
array<char, BUFSIZE> buf;
Scanner(int fd_ = 0) : fd(fd_), idx(0), size(0) {}
inline void refill() {
size = ::read(fd, buf.data(), BUFSIZE);
idx = 0;
}
inline char getch() {
if (idx >= size) {
refill();
if (size == 0) return '\0';
}
return buf[idx++];
}
inline bool skip_space() {
char c = getch();
while (c <= ' ' && c != '\0') c = getch();
if (c == '\0') return false;
idx--;
return true;
}
template<class T>
bool read_signed(T &x) {
if (!skip_space()) {
x = 0;
return false;
}
char c = getch();
bool neg = false;
if (c == '-') {
neg = true;
c = getch();
}
T val = 0;
while ('0' <= c && c <= '9') {
val = val * 10 + (c - '0');
c = getch();
}
x = neg ? -val : val;
return true;
}
template<class T>
bool read_unsigned(T &x) {
if (!skip_space()) {
x = 0;
return false;
}
char c = getch();
T val = 0;
while ('0' <= c && c <= '9') {
val = val * 10 + (c - '0');
c = getch();
}
x = val;
return true;
}
bool read(i32 &x) { return read_signed<i32>(x); }
bool read(i64 &x) { return read_signed<i64>(x); }
bool read(u32 &x) { return read_unsigned<u32>(x); }
bool read(u64 &x) { return read_unsigned<u64>(x); }
template<class T, class U>
bool read(T &x, U &y) { return read(x) && read(y); }
};
struct Printer {
static constexpr size_t BUFSIZE = 1 << 20;
int fd;
size_t idx;
array<char, BUFSIZE> buf;
Printer(int fd_ = 1) : fd(fd_), idx(0) {}
~Printer() {
flush();
}
inline void flush() {
if (idx) {
::write(fd, buf.data(), idx);
idx = 0;
}
}
inline void put_char(char c) {
if (idx == BUFSIZE) flush();
buf[idx++] = c;
}
void write_str(string_view s) {
for (char c : s) put_char(c);
}
template<class T>
void print(const T &x) {
if constexpr (is_same_v<T, string>) write_str(x);
else if constexpr (is_integral_v<T>) {
if (x < 0) { put_char('-'); write_unsigned(-x); }
else write_unsigned(x);
} else write_str("Printer Error");
put_char('\n');
}
template<class T>
void write_unsigned(T x) {
if (x == 0) { put_char('0'); return; }
char s[64]; int n = 0;
while (x > 0) { s[n++] = char('0' + (x % 10)); x /= 10; }
while (n--) put_char(s[n]);
}
};
Scanner in;
Printer out;
#define rep(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define repi(i, a, b) for (i32 i = (i32)(a); i < (i32)(b); ++i)
#define sz(x) ((i32)(x).size())
#define all(x) begin(x), end(x)
template<class F>
struct RecLambda {
F f;
RecLambda(F f_) : f(move(f_)) {}
template<class... Args>
decltype(auto) operator()(Args &&...args) const {
return f(*this, forward<Args>(args)...);
}
};
// Main Solver
void solve() {
int N, M;
in.read(N, M);
VV<int> adj(N);
V<int> deg(N, 0);
rep(i, M) {
int u, v; in.read(u, v); --u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++; deg[v]++;
}
// Basic constraints check
if (M != N - 1) { out.print("No"); return; }
rep(i, N) if(deg[i] > 3) { out.print("No"); return; }
int C1 = 0, C2 = 0, C3 = 0;
rep(i, N) {
if(deg[i] == 1) C1++;
else if(deg[i] == 2) C2++;
else if(deg[i] == 3) C3++;
}
// Helper BFS to compute distances from a set of sources
auto bfs_multi = [&](const V<int>& sources) -> V<int> {
V<int> d(N, -1);
queue<int> q;
for(int s : sources) {
d[s] = 0; q.push(s);
}
while(!q.empty()){
int u = q.front(); q.pop();
for(int v : adj[u]){
if(d[v] == -1){
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d;
};
V<int> leaves, deg3s;
rep(i, N) {
if(deg[i] == 1) leaves.push_back(i);
if(deg[i] == 3) deg3s.push_back(i);
}
V<int> min_dist_leaf = bfs_multi(leaves);
V<int> min_dist_deg3 = bfs_multi(deg3s);
// Group nodes by degree for fast candidate lookup
V<V<int>> nodes_by_deg(4);
rep(i, N) nodes_by_deg[deg[i]].push_back(i);
// Iterate over possible Y
// Y >= 2 because Y-1 >= 1 (distance).
// X = N/Y >= 3.
for (int Y = 2; Y * 3 <= N; ++Y) {
if (N % Y != 0) continue;
int X = N / Y;
// Target counts
// Deg 1: X
// Deg 2: X(Y - 2)
// Deg 3: X
int dC1 = X - C1;
int dC2 = X * (Y - 2) - C2;
int dC3 = X - C3;
V<pii> valid_pair_types;
rep(t1, 3) rep(t2, 3) {
if (t1 > t2) continue;
// simulate delta
int c1 = 0, c2 = 0, c3 = 0;
auto sim = [&](int t) {
if(t == 0) c1++;
if(t == 1) { c1--; c2++; }
if(t == 2) { c2--; c3++; }
};
sim(t1); sim(t2);
if (c1 == dC1 && c2 == dC2 && c3 == dC3) {
valid_pair_types.push_back({t1, t2});
}
}
if (valid_pair_types.empty()) continue;
// Identify Bad Leaves for this Y
V<int> bad_leaves;
for(int l : leaves) {
int d = min_dist_deg3[l];
if (d == -1 || d != Y - 1) {
bad_leaves.push_back(l);
}
}
// Helper check for safety
auto is_safe = [&](int u, int v) -> bool {
bool u_new3 = (deg[u] == 2);
bool v_new3 = (deg[v] == 2);
// Check 1: New deg 3s shouldn't be too close to any leaf
if (u_new3 && min_dist_leaf[u] != -1 && min_dist_leaf[u] < Y - 1) return false;
if (v_new3 && min_dist_leaf[v] != -1 && min_dist_leaf[v] < Y - 1) return false;
// Check 2: Shortcut to old deg 3
if (min_dist_leaf[u] != -1 && min_dist_deg3[v] != -1) {
if (min_dist_leaf[u] + 1 + min_dist_deg3[v] < Y - 1) return false;
}
if (min_dist_leaf[v] != -1 && min_dist_deg3[u] != -1) {
if (min_dist_leaf[v] + 1 + min_dist_deg3[u] < Y - 1) return false;
}
// Check 3: Edge existence
for(int x : adj[u]) if(x == v) return false;
return true;
};
for(auto [t1, t2] : valid_pair_types) {
const V<int>& U_cand = nodes_by_deg[t1];
const V<int>& V_cand = nodes_by_deg[t2];
if (U_cand.empty() || V_cand.empty()) continue;
if (!bad_leaves.empty()) {
int l = bad_leaves[0];
V<int> dist_l = bfs_multi({l});
V<pii> candidates;
// Try to construct valid pairs fixing l
// Method A: u becomes deg 3, dist(l, u) == Y - 1
if (t1 == 2) {
for(int u : U_cand) {
if (dist_l[u] == Y - 1) {
if (min_dist_leaf[u] != -1 && min_dist_leaf[u] < Y - 1) continue;
int limit = 0;
for(int v : V_cand) {
if (u == v) continue;
if (is_safe(u, v)) {
candidates.push_back({u, v});
if(++limit > 80) break;
}
}
}
}
}
// Method B: v becomes deg 3, dist(l, u) + 1 == Y - 1 -> dist(l, u) = Y - 2
if (t2 == 2) {
for(int u : U_cand) {
if (dist_l[u] == Y - 2) {
int limit = 0;
for(int v : V_cand) {
if (u == v) continue;
if (is_safe(u, v)) {
candidates.push_back({u, v});
if(++limit > 80) break;
}
}
}
}
}
// Method C: Connect to old deg 3, dist(l, u) + 1 + dist(v, deg3) == Y - 1
for(int u : U_cand) {
if (dist_l[u] != -1 && dist_l[u] <= Y - 2) {
int rem = Y - 2 - dist_l[u];
int limit = 0;
for(int v : V_cand) {
if (u == v) continue;
if (min_dist_deg3[v] == rem) {
if (is_safe(u, v)) {
candidates.push_back({u, v});
if (++limit > 80) break;
}
}
}
if (candidates.size() > 500) break;
}
}
// Also check symmetric if t1 != t2? Handled by loop or candidates generation?
// The above assumes u has type t1, v has type t2.
// We also need u has type t2, v has type t1.
if (t1 != t2) {
// Same logic with swapped roles
// Or just rely on outer loop iterating all types?
// Outer loop iterates t1 <= t2. So we must check swapped here or ensure logic covers it.
// The logic above generates candidates {u, v} where deg[u]=t1, deg[v]=t2.
// If we swap u,v, we get pair with deg[u]=t2, deg[v]=t1.
// We need to implement swapped logic too?
// Actually, Method A checks if t1==2 (u becomes 3).
// Method B checks if t2==2 (v becomes 3).
// This covers asymmetrical roles.
// Method C iterates u in t1, v in t2.
// We need to also iterate u in t2, v in t1 for Method C?
// Yes.
const V<int>& U2 = nodes_by_deg[t2];
const V<int>& V2 = nodes_by_deg[t1];
// Method C swapped
for(int u : U2) {
if (dist_l[u] != -1 && dist_l[u] <= Y - 2) {
int rem = Y - 2 - dist_l[u];
int limit = 0;
for(int v : V2) {
if (u == v) continue;
if (min_dist_deg3[v] == rem) {
if (is_safe(u, v)) {
candidates.push_back({u, v});
if (++limit > 80) break;
}
}
}
if (candidates.size() > 500) break;
}
}
}
for(auto [u, v] : candidates) {
bool u_becomes_3 = (deg[u] == 2);
bool v_becomes_3 = (deg[v] == 2);
V<int> d_u = bfs_multi({u});
V<int> d_v = bfs_multi({v});
bool ok = true;
for(int bl : bad_leaves) {
int d_new = INF32;
if (min_dist_deg3[bl] != -1) d_new = min_dist_deg3[bl];
if (u_becomes_3 && d_u[bl] != -1) d_new = min(d_new, d_u[bl]);
if (v_becomes_3 && d_v[bl] != -1) d_new = min(d_new, d_v[bl]);
if (d_u[bl] != -1 && min_dist_deg3[v] != -1)
d_new = min(d_new, d_u[bl] + 1 + min_dist_deg3[v]);
if (d_v[bl] != -1 && min_dist_deg3[u] != -1)
d_new = min(d_new, d_v[bl] + 1 + min_dist_deg3[u]);
if (d_new != Y - 1) { ok = false; break; }
}
if (ok) { out.print("Yes"); return; }
}
} else {
// No bad leaves, just find safe pair
int count = 0;
for(int u : U_cand) {
for(int v : V_cand) {
if (u == v) continue;
if (is_safe(u, v)) {
out.print("Yes");
return;
}
if (++count > 500) break;
}
if (count > 500) break;
}
}
}
}
out.print("No");
}
int main() {
solve();
return 0;
}