結果
問題 | No.2588 Increasing Record |
ユーザー |
|
提出日時 | 2023-12-23 20:21:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,418 bytes |
コンパイル時間 | 1,511 ms |
コンパイル使用メモリ | 113,384 KB |
最終ジャッジ日時 | 2025-02-18 14:01:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 23 |
ソースコード
#include <deque>#include <iostream>#include <utility>#include <vector>#include <atcoder/modint>using mint = atcoder::modint998244353;std::vector<mint> naive(int n, const std::vector<std::pair<int, int>>& edges) {std::vector<std::vector<int>> g(n);for (const auto& [u, v] : edges) {g[u].push_back(v);g[v].push_back(u);}std::vector<mint> f(n, 1);for (int x = 0; x < n; ++x) {std::vector<int8_t> vis(n);vis[x] = true;std::deque<int> dq{ x };while (dq.size()) {int u = dq.front();dq.pop_front();for (int v : g[u]) if (not vis[v]) {vis[v] = true;if (v < x) {dq.push_back(v);}if (v > x) {f[v] += f[x];}}}}return f;}#include <atcoder/dsu>#include <algorithm>#include <set>std::vector<mint> solve(int n, const std::vector<std::pair<int, int>>& edges) {atcoder::dsu uf(n);std::vector<std::vector<int>> ts(n);for (const auto& [u, v] : edges) {ts[u].push_back(v);}std::vector<std::set<int>> neighbors(n);std::vector<mint> lazy(n);for (const auto& [u, v] : edges) {neighbors[v].insert(u);}std::vector<mint> f(n, 1);for (int s = 0; s < n; ++s) {std::set<int> cmps_set;for (int t : ts[s]) {cmps_set.insert(uf.leader(t));}std::vector<int> cmps(cmps_set.begin(), cmps_set.end());for (int t : cmps) {uf.merge(s, t);f[s] += lazy[t];lazy[s] += lazy[t];}lazy[s] += f[s];if (cmps.empty()) continue;auto argmax = *std::max_element(cmps.begin(), cmps.end(), [&](int i, int j) { return neighbors[i].size() < neighbors[j].size(); });for (int t : cmps) if (t != argmax) {lazy[s] -= lazy[t];}if (neighbors[argmax].size() < neighbors[s].size()) {argmax = s;}for (int t : cmps) if (t != argmax) {for (int neighbor : neighbors[t]) if (neighbor != s) {f[neighbor] += lazy[t];if (neighbors[argmax].count(neighbor)) {continue;}f[neighbor] -= lazy[argmax];neighbors[argmax].insert(neighbor);}}if (s != argmax) {for (int neighbor : neighbors[s]) if (neighbor != s) {if (neighbors[argmax].count(neighbor)) {continue;}f[neighbor] -= lazy[argmax];neighbors[argmax].insert(neighbor);}}int root = uf.leader(s);std::swap(lazy[root], lazy[s]);std::swap(neighbors[root], neighbors[argmax]);neighbors[root].erase(s);}return f;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<std::pair<int, int>> edges(m);for (auto& [u, v] : edges) {std::cin >> u >> v;--u, --v;if (u < v) {std::swap(u, v);}}mint ans = 0;for (const auto& e : solve(n, edges)) {ans += e;}std::cout << ans.val() << std::endl;}