#780697 (C++17) No.2020 Sum of Common Prefix Length

提出ソース

結果

問題	No.2020 Sum of Common Prefix Length
ユーザー	tokusakurai
提出日時	2022-07-22 22:47:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	207 ms / 2,000 ms
コード長	8,907 bytes
コンパイル時間	3,028 ms
コンパイル使用メモリ	231,460 KB
実行使用メモリ	123,900 KB
最終ジャッジ日時	2024-07-04 07:19:55
合計ジャッジ時間	8,702 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	63 ms 9,728 KB
testcase_08	AC	66 ms 9,728 KB
testcase_09	AC	68 ms 9,728 KB
testcase_10	AC	65 ms 9,728 KB
testcase_11	AC	65 ms 9,856 KB
testcase_12	AC	61 ms 9,856 KB
testcase_13	AC	63 ms 9,728 KB
testcase_14	AC	65 ms 9,856 KB
testcase_15	AC	101 ms 29,056 KB
testcase_16	AC	109 ms 29,056 KB
testcase_17	AC	111 ms 38,384 KB
testcase_18	AC	95 ms 28,152 KB
testcase_19	AC	99 ms 30,252 KB
testcase_20	AC	175 ms 81,908 KB
testcase_21	AC	194 ms 69,184 KB
testcase_22	AC	192 ms 69,124 KB
testcase_23	AC	186 ms 67,932 KB
testcase_24	AC	195 ms 75,916 KB
testcase_25	AC	207 ms 75,116 KB
testcase_26	AC	134 ms 86,192 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	78 ms 16,256 KB
testcase_29	AC	81 ms 16,768 KB
testcase_30	AC	81 ms 15,744 KB
testcase_31	AC	183 ms 99,820 KB
testcase_32	AC	200 ms 123,900 KB
testcase_33	AC	139 ms 85,696 KB
testcase_34	AC	114 ms 42,800 KB
testcase_35	AC	113 ms 42,680 KB
testcase_36	AC	141 ms 80,100 KB
testcase_37	AC	131 ms 53,084 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, x, n) for (int i = x; i <= n; i++)
#define rep3(i, x, n) for (int i = x; i >= n; i--)
#define each(e, v) for (auto &e : v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}

template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}

template <typename T>
int flg(T x, int i) {
    return (x >> i) & 1;
}

template <typename T>
void print(const vector<T> &v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
    if (v.empty()) cout << '\n';
}

template <typename T>
void printn(const vector<T> &v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << '\n';
}

template <typename T>
int lb(const vector<T> &v, T x) {
    return lower_bound(begin(v), end(v), x) - begin(v);
}

template <typename T>
int ub(const vector<T> &v, T x) {
    return upper_bound(begin(v), end(v), x) - begin(v);
}

template <typename T>
void rearrange(vector<T> &v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <typename T>
vector<int> id_sort(const vector<T> &v, bool greater = false) {
    int n = v.size();
    vector<int> ret(n);
    iota(begin(ret), end(ret), 0);
    sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });
    return ret;
}

template <typename S, typename T>
pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {
    return make_pair(p.first + q.first, p.second + q.second);
}

template <typename S, typename T>
pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {
    return make_pair(p.first - q.first, p.second - q.second);
}

template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &p) {
    S a;
    T b;
    is >> a >> b;
    p = make_pair(a, b);
    return is;
}

template <typename S, typename T>
ostream &operator<<(ostream &os, const pair<S, T> &p) {
    return os << p.first << ' ' << p.second;
}

struct io_setup {
    io_setup() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;

const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
const int MOD = 1000000007;
// const int MOD = 998244353;

template <typename T>
struct Binary_Indexed_Tree {
    vector<T> bit;
    const int n;

    Binary_Indexed_Tree(const vector<T> &v) : n((int)v.size()) {
        bit.resize(n + 1);
        copy(begin(v), end(v), begin(bit) + 1);
        for (int a = 2; a <= n; a <<= 1) {
            for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
        }
    }

    Binary_Indexed_Tree(int n, const T &x) : n(n) {
        bit.resize(n + 1);
        vector<T> v(n, x);
        copy(begin(v), end(v), begin(bit) + 1);
        for (int a = 2; a <= n; a <<= 1) {
            for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
        }
    }

    void add(int i, const T &x) {
        for (i++; i <= n; i += (i & -i)) bit[i] += x;
    }

    void change(int i, const T &x) { add(i, x - query(i, i + 1)); }

    T sum(int i) const {
        T ret = 0;
        for (; i > 0; i -= (i & -i)) ret += bit[i];
        return ret;
    }

    T query(int l, int r) const { return sum(r) - sum(l); }

    T operator[](int i) const { return query(i, i + 1); }

    int lower_bound(T x) const {
        int ret = 0;
        for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
            if (ret + (1 << k) <= n && bit[ret + (1 << k)] < x) x -= bit[ret += (1 << k)];
        }
        return ret;
    }

    int upper_bound(T x) const {
        int ret = 0;
        for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
            if (ret + (1 << k) <= n && bit[ret + (1 << k)] <= x) x -= bit[ret += (1 << k)];
        }
        return ret;
    }
};

template <bool directed = false>
struct Heavy_Light_Decomposition {
    struct edge {
        int to, id;
        edge(int to, int id) : to(to), id(id) {}
    };

    vector<vector<edge>> es;
    vector<int> par, si, depth;
    vector<int> root;       // 属する連結成分の根
    vector<int> id_v, id_e; // 各頂点、各辺が一列に並べたときに何番目に相当するか（辺の番号は 1,2,...,n-1 となることに注意）
    const int n;
    int m;

    Heavy_Light_Decomposition(int n) : es(n), par(n), si(n), depth(n), root(n), id_v(n), id_e(n - 1), n(n), m(0) {}

    void add_edge(int from, int to) {
        es[from].emplace_back(to, m);
        if (!directed) es[to].emplace_back(from, m);
        m++;
    }

    int _dfs1(int now, int pre = -1) {
        par[now] = pre;
        if (pre == -1) depth[now] = 0;
        si[now] = 1;
        for (auto &e : es[now]) {
            if (e.to != pre) {
                depth[e.to] = depth[now] + 1;
                si[now] += _dfs1(e.to, now);
            }
        }
        return si[now];
    }

    void _dfs2(int now, bool st, int &s, int pre = -1) {
        root[now] = (st ? now : root[pre]);
        id_v[now] = s++;
        edge heavy = {-1, -1};
        int M = 0;
        for (auto &e : es[now]) {
            if (e.to == pre) continue;
            if (M < si[e.to]) M = si[e.to], heavy = e;
        }
        if (heavy.id != -1) {
            id_e[heavy.id] = s;
            _dfs2(heavy.to, false, s, now);
        }
        for (auto &e : es[now]) {
            if (e.to != pre && e.id != heavy.id) {
                id_e[e.id] = s;
                _dfs2(e.to, true, s, now);
            }
        }
    }

    void decompose(int root = 0) {
        _dfs1(root);
        int s = 0;
        _dfs2(root, true, s);
    }

    vector<pair<int, int>> get_path(int u, int v, bool use_edge = false) { // パスに対応する区間たちを列挙
        vector<pair<int, int>> ret;
        while (root[u] != root[v]) {
            if (depth[root[u]] > depth[root[v]]) swap(u, v);
            ret.emplace_back(id_v[root[v]], id_v[v] + 1);
            v = par[root[v]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        ret.emplace_back(id_v[u] + use_edge, id_v[v] + 1);
        return ret;
    }

    vector<pair<int, int>> get_path_noncommutative(int u, int v, bool use_edge = false) { // クエリが非可換の場合
        vector<pair<int, int>> l, r;
        while (root[u] != root[v]) {
            if (depth[root[u]] > depth[root[v]]) {
                l.emplace_back(id_v[u] + 1, id_v[root[u]]);
                u = par[root[u]];
            } else {
                r.emplace_back(id_v[root[v]], id_v[v] + 1);
                v = par[root[v]];
            }
        }
        if (depth[u] > depth[v]) {
            l.emplace_back(id_v[u] + 1, id_v[v] + use_edge);
        } else {
            r.emplace_back(id_v[u] + use_edge, id_v[v] + 1);
        }
        reverse(begin(r), end(r));
        for (auto &e : r) l.push_back(e);
        return l;
    }
};

int main() {
    int N;
    cin >> N;

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    int Q;
    cin >> Q;

    vector<int> t(Q), id(Q);
    vector<char> c(Q);
    vector<string> T = S;

    rep(i, Q) {
        cin >> t[i] >> id[i];
        id[i]--;
        if (t[i] == 1) {
            cin >> c[i];
            T[id[i]] += c[i];
        }
    }
    // rep(i, N) cout << T[i] << '\n';

    vector<vector<int>> ptr(N);
    int K = 1;

    vector<vector<int>> chi(1, vector<int>(26, -1));
    rep(i, N) {
        int now = 0;
        each(e, T[i]) {
            int x = e - 'a';
            if (chi[now][x] == -1) {
                chi[now][x] = K;
                chi.eb(26, -1);
                K++;
            }
            now = chi[now][x];
            ptr[i].eb(now);
        }
    }

    vector<ll> a(K, 0);
    rep(i, N) {
        int L = sz(S[i]);
        rep(j, L) a[ptr[i][j]]++;
    }

    // cout << K << '\n';

    Heavy_Light_Decomposition G(K);
    rep(i, K) {
        rep(j, 26) {
            if (chi[i][j] != -1) G.add_edge(i, chi[i][j]);
        }
    }
    // print(a);

    G.decompose();
    vector<ll> b(K, 0);
    rep(i, K) b[G.id_v[i]] = a[i];

    Binary_Indexed_Tree<ll> bit(b);
    vector<int> L(N);
    rep(i, N) L[i] = sz(S[i]) - 1;

    rep(i, Q) {
        int e = id[i];
        if (t[i] == 1) {
            int p = ptr[e][++L[e]];
            bit.add(G.id_v[p], 1);
        } else {
            int u = 0, v = ptr[e][L[e]];
            ll ans = 0;
            for (auto e : G.get_path(u, v)) ans += bit.query(e.first, e.second);
            cout << ans << '\n';
        }
    }
}

yukicoder

結果

テストケース

ソースコード