結果
| 問題 | No.2588 Increasing Record |
| ユーザー |
👑  rin204
|
| 提出日時 | 2023-11-24 15:39:49 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 362 ms / 3,000 ms |
| コード長 | 6,723 bytes |
| コンパイル時間 | 3,996 ms |
| コンパイル使用メモリ | 285,760 KB |
| 実行使用メモリ | 36,528 KB |
| 最終ジャッジ日時 | 2024-09-27 06:39:44 |
| 合計ジャッジ時間 | 15,334 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 44 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include "atcoder/fenwicktree.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
struct UnionFind {
int n;
vector<int> par;
vector<int> mx;
UnionFind(int n) : n(n), par(n, -1), mx(n) {
iota(mx.begin(), mx.end(), 0);
}
int find(int x) {
if (par[x] < 0) return x;
return par[x] = find(par[x]);
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
mx[u] = max(mx[u], mx[v]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
int get_max(int u) {
return mx[find(u)];
}
};
struct HLD {
int n, path;
std::vector<std::vector<int>> edges;
std::vector<int> siz;
std::vector<int> par;
std::vector<int> depth;
std::vector<int> path_ind;
std::vector<int> path_root;
std::vector<int> heavy_child;
std::vector<bool> isheavy;
std::vector<int> L;
std::vector<int> R;
HLD(int n) : n(n) {
edges.resize(n);
siz.assign(n, -1);
par.assign(n, -1);
depth.assign(n, -1);
path_ind.assign(n, -1);
heavy_child.assign(n, -1);
isheavy.assign(n, false);
L.assign(n, -1);
R.assign(n, -1);
}
void read_edges(int indexed = 1) {
int u, v;
for (int i = 0; i < n - 1; i++) {
std::cin >> u >> v;
u -= indexed;
v -= indexed;
edges[u].push_back(v);
edges[v].push_back(u);
}
}
void add_edge(int u, int v) {
edges[u].push_back(v);
edges[v].push_back(u);
}
void build(int root = 0) {
depth[root] = 0;
std::stack<int> st;
std::vector<int> route;
st.push(root);
route.push_back(root);
while (!st.empty()) {
int pos = st.top();
st.pop();
for (auto npos : edges[pos]) {
if (depth[npos] == -1) {
depth[npos] = depth[pos] + 1;
par[npos] = pos;
st.push(npos);
route.push_back(npos);
}
}
}
reverse(route.begin(), route.end());
for (auto pos : route) {
siz[pos] = 1;
int ma = -1;
for (auto npos : edges[pos]) {
if (depth[npos] > depth[pos]) siz[pos] += siz[npos];
if (siz[npos] > ma) {
ma = siz[npos];
heavy_child[pos] = npos;
}
}
if (heavy_child[pos] != -1) isheavy[heavy_child[pos]] = true;
}
isheavy[root] = true;
path = 0;
st.push(~root);
st.push(root);
path_root.push_back(root);
int cc = 0;
while (!st.empty()) {
int pos = st.top();
st.pop();
if (pos >= 0) {
L[pos] = cc++;
if (!isheavy[pos]) {
path++;
path_root.push_back(pos);
}
path_ind[pos] = path;
for (auto npos : edges[pos]) {
if (npos == par[pos] || npos == heavy_child[pos]) continue;
st.push(~npos);
st.push(npos);
}
if (heavy_child[pos] != -1) {
int npos = heavy_child[pos];
st.push(~npos);
st.push(npos);
}
} else {
pos = ~pos;
R[pos] = cc;
}
}
}
std::vector<std::pair<int, int>> get_path(int u, int v) {
std::vector<int> ll;
std::vector<int> rr;
ll.push_back(u);
rr.push_back(v);
while (path_ind[u] != path_ind[v]) {
if (depth[path_root[path_ind[u]]] >= depth[path_root[path_ind[v]]]) {
u = path_root[path_ind[u]];
ll.push_back(u);
u = par[u];
ll.push_back(u);
} else {
v = path_root[path_ind[v]];
rr.push_back(v);
v = par[v];
rr.push_back(v);
}
}
reverse(rr.begin(), rr.end());
ll.insert(ll.end(), rr.begin(), rr.end());
int n = ll.size();
std::vector<std::pair<int, int>> res(n / 2);
for (int i = 0; i < n; i += 2) {
res[i / 2] = {ll[i], ll[i + 1]};
}
return res;
}
int lca(int u, int v) {
while (path_ind[u] != path_ind[v]) {
if (depth[path_root[path_ind[u]]] >= depth[path_root[path_ind[v]]])
u = par[path_root[path_ind[u]]];
else
v = par[path_root[path_ind[v]]];
}
return (depth[u] <= depth[v]) ? u : v;
}
int dist(int u, int v) {
int p = lca(u, v);
return depth[u] + depth[v] - 2 * depth[p];
}
template <typename T>
std::vector<T> reorder(std::vector<T> &A, bool rev = false) {
assert(int(A.size()) == n);
std::vector<T> ret(n);
for (int i = 0; i < n; i++) {
ret[L[i]] = A[i];
}
if (rev) reverse(ret.begin(), ret.end());
return ret;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector E(n, vector<int>());
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
E[v - 1].emplace_back(u - 1);
}
UnionFind UF(n);
HLD hld(n);
for (int v = 0; v < n; v++) {
for (auto u : E[v]) {
if (!UF.same(u, v)) {
hld.add_edge(UF.get_max(u), v);
UF.unite(u, v);
}
}
}
hld.build();
atcoder::fenwick_tree<mint> bit(n);
for (int v = 0; v < n; v++) {
vector<pair<int, int>> lr;
for (auto u : E[v]) {
auto path = hld.get_path(u, v);
for (auto [uu, vv] : path) {
uu = hld.L[uu];
vv = hld.L[vv];
if (uu > vv) swap(uu, vv);
lr.emplace_back(uu, vv + 1);
}
}
sort(lr.begin(), lr.end());
mint tot = 0;
int mar = 0;
for (auto [l, r] : lr) {
l = max(l, mar);
if (l < r) {
tot += bit.sum(l, r);
}
mar = max(mar, r);
}
bit.add(hld.L[v], tot + 1);
}
mint ans = bit.sum(0, n);
cout << ans.val() << endl;
}
int main() {
solve();
}