結果
| 問題 |
No.2595 Parsing Challenge
|
| コンテスト | |
| ユーザー |
 Forested
|
| 提出日時 | 2023-12-22 18:43:48 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 910 ms / 6,000 ms |
| コード長 | 20,653 bytes |
| コンパイル時間 | 6,824 ms |
| コンパイル使用メモリ | 317,148 KB |
| 実行使用メモリ | 160,432 KB |
| 最終ジャッジ日時 | 2024-09-27 11:37:19 |
| 合計ジャッジ時間 | 25,775 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 55 |
ソースコード
#ifndef LOCAL
#define FAST_IO
#endif
// ============
#include <bits/stdc++.h>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(x.size())
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
using pi = pair<i32, i32>;
using pl = pair<i64, i64>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;
template <typename T>
using PQR = priority_queue<T, V<T>, greater<T>>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <typename T>
i32 lob(const V<T> &arr, const T &v) {
return (i32)(lower_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
i32 upb(const V<T> &arr, const T &v) {
return (i32)(upper_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
V<i32> argsort(const V<T> &arr) {
V<i32> ret;
iota(ALL(ret), 0);
sort(ALL(ret), [&](i32 i, i32 j) -> bool {
if (arr[i] == arr[j]) {
return i < j;
} else {
return arr[i] < arr[j];
}
});
return ret;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
istream &operator>>(istream &is, i128 &x) {
i64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, i128 x) {
os << (i64)x;
return os;
}
istream &operator>>(istream &is, u128 &x) {
u64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, u128 x) {
os << (u64)x;
return os;
}
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
void scan(char &x) { cin >> x; }
void scan(u32 &x) { cin >> x; }
void scan(u64 &x) { cin >> x; }
void scan(i32 &x) { cin >> x; }
void scan(i64 &x) { cin >> x; }
void scan(string &x) { cin >> x; }
template <typename T>
void scan(V<T> &x) {
for (T &ele : x) {
scan(ele);
}
}
void read() {}
template <typename Head, typename... Tail>
void read(Head &head, Tail &...tail) {
scan(head);
read(tail...);
}
#define CHAR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define U32(...) u32 __VA_ARGS__; read(__VA_ARGS__);
#define U64(...) u64 __VA_ARGS__; read(__VA_ARGS__);
#define I32(...) i32 __VA_ARGS__; read(__VA_ARGS__);
#define I64(...) i64 __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define VEC(type, name, size) V<type> name(size); read(name);
#define VVEC(type, name, size1, size2) VV<type> name(size1, V<type>(size2)); read(name);
// ============
#ifdef DEBUGF
#else
#define DBG(x) (void) 0
#endif
// ============
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
class HeavyLightDecomposition {
std::vector<int> siz;
std::vector<int> par;
std::vector<int> hea;
std::vector<int> in;
std::vector<int> out;
std::vector<int> dep;
std::vector<int> rev;
template <typename G>
void dfs1(G &g, int v) {
if (!g[v].empty() && (int) g[v][0] == par[v]) {
std::swap(g[v][0], g[v].back());
}
for (auto &e : g[v]) {
int u = (int)e;
if (u != par[v]) {
par[u] = v;
dfs1(g, u);
siz[v] += siz[u];
if (siz[u] > siz[(int) g[v][0]]) {
std::swap(g[v][0], e);
}
}
}
}
template <typename G>
void dfs2(const G &g, int v, int &time) {
in[v] = time;
rev[time++] = v;
for (auto &e : g[v]) {
int u = (int)e;
if (u == par[v]) {
continue;
}
if (u == (int) g[v][0]) {
hea[u] = hea[v];
} else {
hea[u] = u;
}
dep[u] = dep[v] + 1;
dfs2(g, u, time);
}
out[v] = time;
}
public:
template <typename G>
HeavyLightDecomposition(G &g, int root = 0) :
siz(g.size(), 1),
par(g.size(), root),
hea(g.size(), root),
in(g.size(), 0),
out(g.size(), 0),
dep(g.size(), 0),
rev(g.size(), 0) {
assert(root >= 0 && root < (int) g.size());
dfs1(g, root);
int time = 0;
dfs2(g, root, time);
}
int subtree_size(int v) const {
assert(v >= 0 && v < (int) siz.size());
return siz[v];
}
int parent(int v) const {
assert(v >= 0 && v < (int) par.size());
return par[v];
}
int in_time(int v) const {
assert(v >= 0 && v < (int) in.size());
return in[v];
}
int out_time(int v) const {
assert(v >= 0 && v < (int) out.size());
return out[v];
}
int depth(int v) const {
assert(v >= 0 && v < (int) dep.size());
return dep[v];
}
int time_to_vertex(int t) const {
assert(t >= 0 && t < (int) rev.size());
return rev[t];
}
int head(int v) const {
assert(v >= 0 && v < (int) out.size());
return hea[v];
}
int la(int v, int k) const {
assert(v >= 0 && v < (int) dep.size());
assert(k >= 0);
if (k > dep[v]) {
return -1;
}
while (true) {
int u = hea[v];
if (in[u] + k <= in[v]) {
return rev[in[v] - k];
}
k -= in[v] - in[u] + 1;
v = par[u];
}
return 0;
}
int forward(int v, int dst) const {
assert(v >= 0 && v < (int) dep.size());
assert(dst >= 0 && dst < (int) dep.size());
assert(v != dst);
int l = lca(v, dst);
if (l == v) {
return la(dst, dep[dst] - dep[v] - 1);
} else {
return par[v];
}
}
int lca(int u, int v) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
while (u != v) {
if (in[u] > in[v]) {
std::swap(u, v);
}
if (hea[u] == hea[v]) {
v = u;
} else {
v = par[hea[v]];
}
}
return u;
}
int dist(int u, int v) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
std::vector<std::pair<int, int>> path(int u, int v, bool edge) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
std::vector<std::pair<int, int>> fromu, fromv;
bool rev = false;
while (true) {
if (u == v && edge) {
break;
}
if (in[u] > in[v]) {
std::swap(u, v);
std::swap(fromu, fromv);
rev ^= true;
}
if (hea[u] == hea[v]) {
fromv.emplace_back(in[v], in[u] + (int)edge);
v = u;
break;
} else {
fromv.emplace_back(in[v], in[hea[v]]);
v = par[hea[v]];
}
}
if (rev) {
std::swap(fromu, fromv);
}
std::reverse(fromv.begin(), fromv.end());
fromu.reserve(fromv.size());
for (auto [x, y] : fromv) {
fromu.emplace_back(y, x);
}
return fromu;
}
int jump(int u, int v, int k) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
assert(k >= 0);
int l = lca(u, v);
int dis = dep[u] + dep[v] - 2 * dep[l];
if (k > dis) {
return -1;
}
if (k <= dep[u] - dep[l]) {
return la(u, k);
} else {
return la(v, dis - k);
}
}
int meet(int u, int v, int w) const {
return lca(u, v) ^ lca(v, w) ^ lca(w, u);
}
};
// ============
// ============
#include <atcoder/convolution>
#include <compare>
#include <iostream>
#include <string>
class BigInt {
static constexpr long long B = 1000000;
static constexpr int L = 6;
// a >= 0
static void normalize(std::vector<long long> &a) {
if (a.empty()) {
return;
}
for (int i = 0; i < (int)a.size() - 1; ++i) {
if (a[i] < 0) {
long long v = (-a[i] + B - 1) / B;
a[i] += v * B;
a[i + 1] -= v;
}
if (a[i] >= B) {
long long v = a[i] / B;
a[i] -= v * B;
a[i + 1] += v;
}
}
while (a.back() >= B) {
long long v = a.back() / B;
a.back() -= v * B;
a.push_back(v);
}
while (!a.empty() && a.back() == 0) {
a.pop_back();
}
}
static std::vector<long long> nn_add(const std::vector<long long> &lhs, const std::vector<long long> rhs) {
std::vector<long long> ret(std::max(lhs.size(), rhs.size()), 0);
for (int i = 0; i < (int)lhs.size(); ++i) {
ret[i] += lhs[i];
}
for (int i = 0; i < (int)rhs.size(); ++i) {
ret[i] += rhs[i];
}
normalize(ret);
return ret;
}
// lhs >= rhs
static std::vector<long long> nn_sub(const std::vector<long long> &lhs, const std::vector<long long> rhs) {
std::vector<long long> ret(lhs.size(), 0);
for (int i = 0; i < (int)lhs.size(); ++i) {
ret[i] += lhs[i];
}
for (int i = 0; i < (int)rhs.size(); ++i) {
ret[i] -= rhs[i];
}
normalize(ret);
return ret;
}
static std::vector<long long> nn_mul(const std::vector<long long> &lhs, const std::vector<long long> rhs) {
std::vector<long long> ret = atcoder::convolution_ll(lhs, rhs);
normalize(ret);
return ret;
}
static std::strong_ordering cmp(const std::vector<long long> &lhs, const std::vector<long long> &rhs) {
if (lhs.size() != rhs.size()) {
return lhs.size() <=> rhs.size();
} else {
for (int i = (int)lhs.size() - 1; i >= 0; --i) {
if (lhs[i] != rhs[i]) {
return lhs[i] <=> rhs[i];
}
}
return std::strong_ordering::equivalent;
}
}
std::vector<long long> expr;
bool pos;
BigInt(std::vector<long long> expr, bool pos) : expr(expr), pos(pos) {}
public:
BigInt() : expr(), pos(true) {}
BigInt(long long x) : expr(), pos(true) {
if (x < 0) {
pos = false;
x = -x;
}
while (x > 0) {
expr.push_back(x % B);
x /= B;
}
}
// [0-9]*
BigInt(const std::string &s) : expr(), pos(true) {
int cur = (int)s.size();
while (cur > 0) {
int nx = std::max(0, cur - 6);
long long val = 0;
long long p = 1;
for (int i = cur - 1; i >= nx; --i) {
val += p * (s[i] - '0');
p *= 10;
}
expr.push_back(val);
cur = nx;
}
}
int size() const {
return (int)expr.size();
}
const BigInt operator-() const {
return BigInt(expr, !pos);
}
BigInt &operator+=(const BigInt &rhs) {
if (pos == rhs.pos) {
expr = nn_add(expr, rhs.expr);
} else {
auto c = cmp(expr, rhs.expr);
if (c > 0) {
expr = nn_sub(expr, rhs.expr);
} else if (c < 0) {
expr = nn_sub(rhs.expr, expr);
pos = !pos;
} else {
expr.clear();
}
}
return *this;
}
BigInt &operator-=(const BigInt &rhs) {
if (pos != rhs.pos) {
expr = nn_add(expr, rhs.expr);
} else {
auto c = cmp(expr, rhs.expr);
if (c > 0) {
expr = nn_sub(expr, rhs.expr);
} else if (c < 0) {
expr = nn_sub(rhs.expr, expr);
pos = !pos;
} else {
expr.clear();
}
}
return *this;
}
BigInt &operator*=(const BigInt &rhs) {
expr = nn_mul(expr, rhs.expr);
pos ^= !rhs.pos;
return *this;
}
friend BigInt operator+(BigInt lhs, const BigInt &rhs) {
lhs += rhs;
return lhs;
}
friend BigInt operator-(BigInt lhs, const BigInt &rhs) {
lhs -= rhs;
return lhs;
}
friend BigInt operator*(BigInt lhs, const BigInt &rhs) {
lhs *= rhs;
return lhs;
}
std::string to_string() const {
if (expr.empty()) {
return std::string("0");
}
std::string ret;
if (!pos) {
ret.push_back('-');
}
for (int i = (int)expr.size() - 1; i >= 0; --i) {
std::string s = std::to_string(expr[i]);
if (i != (int)expr.size() - 1) {
s = std::string(6 - (int)s.size(), '0') + s;
}
ret += s;
}
return ret;
}
};
std::istream &operator>>(std::istream &is, BigInt &v) {
std::string s;
is >> s;
int p = 0;
bool pos = true;
while (p < (int)s.size() && s[p] == '-') {
pos = !pos;
++p;
}
v = BigInt(s.substr(p));
if (!pos) {
v = -v;
}
return is;
}
std::ostream &operator<<(std::ostream &os, const BigInt &v) {
os << v.to_string();
return os;
}
// ============
template <typename Op>
typename Op::Value weighted_merge(const V<typename Op::Value> &vals) {
using Val = typename Op::Value;
auto rec = [&](auto rec, i32 l, i32 r) -> Val {
if (r - l == 1) {
return vals[l];
}
i32 s = 0;
REP(i, l, r) {
s += vals[i].size();
}
i32 c = 0;
REP(i, l, r) {
c += vals[i].size();
if (2 * c >= s) {
Val ret = vals[i];
if (i != l) {
ret = Op::op(rec(rec, l, i), ret);
}
if (i != r - 1) {
ret = Op::op(ret, rec(rec, i + 1, r));
}
return ret;
}
}
assert(false);
};
return rec(rec, 0, LEN(vals));
}
using bigint = BigInt;
struct Affine {
bigint a, b;
Affine() : a(1LL), b(0LL) {}
Affine(bigint a, bigint b) : a(a), b(b) {}
i32 size() const {
return max(a.size(), b.size());
}
};
struct Op {
using Value = Affine;
static Affine op(const Affine f, const Affine g) {
return Affine(f.a * g.a, f.a * g.b + f.b);
}
};
struct Parser {
string s;
i32 it;
// results
VV<i32> tree;
V<bigint> val;
V<char> op;
i32 root;
i32 new_node() {
i32 v = LEN(tree);
tree.push_back(V<i32>());
val.push_back(bigint());
op.push_back('!');
return v;
}
i32 number() {
bool pos = true;
while (it < (i32)s.size() && s[it] == '-') {
pos = !pos;
++it;
}
string d;
while (it < (i32)s.size() && isdigit(s[it])) {
d.push_back(s[it]);
++it;
}
i32 v = new_node();
val[v] = bigint(d);
if (!pos) {
val[v] = -val[v];
}
return v;
}
i32 factor() {
if (s[it] == '(') {
++it;
i32 v = expr();
assert(it < (i32)s.size() && s[it] == ')');
++it;
return v;
} else {
i32 v = number();
return v;
}
}
i32 term() {
i32 r = factor();
while (it < (i32)s.size() && s[it] == '*') {
++it;
i32 u = r;
i32 v = factor();
r = new_node();
op[r] = '*';
tree[r].push_back(u);
tree[r].push_back(v);
}
return r;
}
i32 expr() {
i32 r = term();
while (it < (i32)s.size() && (s[it] == '+' || s[it] == '-')) {
if (s[it] == '+') {
++it;
i32 u = r;
i32 v = term();
r = new_node();
op[r] = '+';
tree[r].push_back(u);
tree[r].push_back(v);
} else {
++it;
i32 v = term();
// negate
{
i32 m = new_node();
val[m] = bigint(-1LL);
i32 t = new_node();
op[t] = '*';
tree[t].push_back(v);
tree[t].push_back(m);
v = t;
}
// add
i32 u = r;
r = new_node();
op[r] = '+';
tree[r].push_back(u);
tree[r].push_back(v);
}
}
return r;
}
Parser(string s) : s(s), it(0), tree(), val(), op(), root(-1) {
root = expr();
}
};
// 末尾から適用する
bigint affine(const V<char> &op, const V<bigint> &val, const bigint &x) {
assert(op.size() == val.size());
/*bigint ans = x;
PER(i, op.size()) {
if (op[i] == '+') {
ans += val[i];
} else if (op[i] == '-') {
ans -= val[i];
} else {
ans *= val[i];
}
}
return ans;*/
/*// x -> ax+b
auto rec = [&](auto rec, i32 l, i32 r) -> pair<bigint, bigint> {
if (r - l == 1) {
if (op[l] == '+') {
return pair<bigint, bigint>(bigint(1LL), val[l]);
} else if (op[l] == '-') {
return pair<bigint, bigint>(bigint(1LL), -val[l]);
} else {
return pair<bigint, bigint>(val[l], bigint());
}
}
i32 mid = (l + r) / 2;
auto [al, bl] = rec(rec, l, mid);
auto [ar, br] = rec(rec, mid, r);
return pair<bigint, bigint>(al * ar, al * br + bl);
};
auto [a, b] = rec(rec, 0, (i32)op.size());
return a * x + b;*/
V<Affine> funcs;
REP(i, LEN(op)) {
if (op[i] == '+') {
funcs.emplace_back(Affine(bigint(1LL), val[i]));
} else if (op[i] == '-') {
funcs.emplace_back(Affine(bigint(1LL), -val[i]));
} else {
funcs.emplace_back(Affine(val[i], bigint(0LL)));
}
}
Affine tot = weighted_merge<Op>(funcs);
return tot.a * x + tot.b;
}
int main() {
i32 n;
cin >> n;
string s;
cin >> s;
Parser parser(s);
HeavyLightDecomposition hld(parser.tree, parser.root);
V<i32> heavy(parser.tree.size(), -1), light(parser.tree.size(), -1);
REP(i, parser.tree.size()) {
if (parser.tree[i].empty()) {
continue;
}
i32 u = parser.tree[i][0], v = parser.tree[i][1];
if (hld.head(u) == u) {
heavy[i] = v;
light[i] = u;
} else {
heavy[i] = u;
light[i] = v;
}
}
auto solve = [&](auto solve, i32 v) -> bigint {
if (heavy[v] == -1) {
return parser.val[v];
}
V<char> op;
V<bigint> val;
i32 cur = v;
while (heavy[cur] != -1) {
op.push_back(parser.op[cur]);
val.push_back(solve(solve, light[cur]));
cur = heavy[cur];
}
return affine(op, val, solve(solve, cur));
};
cout << solve(solve, parser.root) << '\n';
}