結果

問題 No.1494 LCS on Tree
ユーザー sapphire__15sapphire__15
提出日時 2021-04-30 23:33:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 3,898 bytes
コンパイル時間 1,417 ms
コンパイル使用メモリ 140,808 KB
実行使用メモリ 142,464 KB
最終ジャッジ日時 2024-04-30 17:48:19
合計ジャッジ時間 6,228 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 166 ms
139,648 KB
testcase_04 AC 102 ms
21,888 KB
testcase_05 AC 107 ms
21,332 KB
testcase_06 AC 104 ms
21,804 KB
testcase_07 AC 108 ms
21,496 KB
testcase_08 AC 105 ms
21,116 KB
testcase_09 AC 111 ms
21,396 KB
testcase_10 AC 104 ms
22,856 KB
testcase_11 AC 105 ms
21,272 KB
testcase_12 AC 99 ms
21,420 KB
testcase_13 AC 97 ms
21,032 KB
testcase_14 AC 166 ms
142,464 KB
testcase_15 AC 164 ms
128,256 KB
testcase_16 AC 144 ms
84,736 KB
testcase_17 AC 159 ms
105,472 KB
testcase_18 AC 157 ms
96,896 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 1 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 167 ms
139,520 KB
testcase_31 AC 168 ms
121,728 KB
testcase_32 AC 150 ms
91,520 KB
testcase_33 AC 150 ms
87,936 KB
testcase_34 AC 151 ms
87,936 KB
testcase_35 AC 7 ms
6,940 KB
testcase_36 AC 32 ms
8,812 KB
testcase_37 AC 8 ms
6,944 KB
testcase_38 AC 28 ms
8,492 KB
testcase_39 AC 45 ms
11,752 KB
testcase_40 AC 16 ms
6,944 KB
testcase_41 AC 85 ms
16,768 KB
testcase_42 AC 18 ms
6,944 KB
testcase_43 AC 64 ms
16,068 KB
testcase_44 AC 48 ms
12,824 KB
testcase_45 AC 125 ms
50,816 KB
testcase_46 AC 127 ms
50,816 KB
testcase_47 AC 114 ms
50,816 KB
testcase_48 AC 121 ms
50,944 KB
testcase_49 AC 117 ms
50,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <functional>
#include <cassert>
#include <stack>
#include <numeric>
#include <iomanip>
#include <limits>
#include <random>
#include <unordered_map>

typedef int64_t ll;
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> Pdd;

#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)
#define all(_l) _l.begin(), _l.end()
#define rall(_l) _l.rbegin(), _l.rend()
#define MM << " " <<

template<typename _T>
using MaxHeap = std::priority_queue<_T>;
template<typename _T>
using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;

template<typename _T>
inline bool chmax(_T &_l, const _T _b) {
    if (_l < _b) {
        _l = _b;
        return true;
    }
    return false;
}
template<typename _T>
inline bool chmin(_T &_l, const _T _b) {
    if (_l > _b) {
        _l = _b;
        return true;
    }
    return false;
}

template<typename _T>
void vdeb(const std::vector<_T> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename _T>
void vdeb(const std::vector<std::vector<_T>> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        // std::cout << i << ' ';
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

using namespace std;

int N;
string s;

struct Edge {
    int to;
    char c;
    Edge() {}
    Edge(int _to, char _c) : to(_to),c(_c) {}
};

struct DP {
    int n;
    vector<int> dp;
    // DP() {}
    DP(int _n = s.size()) : n(_n), dp(n) {}
    DP addroot(char c) {
        DP ret(*this);
        rip(i,n,0) {
            if(i) ret.dp[i] = max(max(ret.dp[i-1], dp[i]), dp[i-1] + ((s[i] == c) ? 1 : 0));
            else ret.dp[i] = max((s[i] == c) ? 1 : 0, dp[i]);
        }
        return ret;
    }
    DP& operator+=(const DP &other) {
        rip(i,n,0) chmax(dp[i], other.dp[i]);
        return *this;
    }
    DP operator+(const DP &other) {
        DP ret(*this);
        rip(i,n,0) chmax(ret.dp[i], other.dp[i]);
        return ret;
    }
};

void dfs1(vector<vector<Edge>> &da, vector<DP> &dp, int pare = -1, int child = 0) {
    for(int i = 0; i < int(da[child].size()); i++){
        if(da[child][i].to == pare) continue;
        dfs1(da, dp, child, da[child][i].to);
        dp[child] += dp[da[child][i].to].addroot(da[child][i].c);
    }
}

void dfs2(vector<vector<Edge>> &da, vector<DP> &ans, const DP &dp = DP(), int pare = -1, int child = 0){
    if(pare != -1) ans[child] += dp;
    int size = da[child].size();
    vector<DP> dpL(size+1) ,dpR(size+1);
    for(int i = 0;i < size; i++){
        int next = da[child][i].to;
        dpL[i+1] = dpL[i];
        if(next == pare) dpL[i+1] += dp;
        else dpL[i+1] += ans[next].addroot(da[child][i].c);
    }
    for(int i = size; i > 0; i--){
        int next = da[child][i-1].to;
        dpR[i-1] = dpR[i];
        if(next == pare) dpR[i-1] += dp;
        else dpR[i-1] +=  ans[next].addroot(da[child][i-1].c);
    }
    for(int i = 0;i < size;i++){
        int next = da[child][i].to;
        if(next == pare) continue;
        dfs2(da, ans, (dpL[i] + dpR[i+1]).addroot(da[child][i].c), child, next);
    }
}

void rooting(vector<vector<Edge>> &da, vector<DP> &dp) {
    dfs1(da, dp);
    dfs2(da, dp);
}

int main() {
    cin >> N;
    cin >> s;
    vector<vector<Edge>> da(N, vector<Edge>(0));
    rip(i,N-1,0) {
        int x, y; cin >> x >> y;
        char c; cin >> c;
        --x; --y;
        da[y].push_back({x, c});
        da[x].push_back({y, c});
    }
    vector<DP> dp(N, s.size());
    rooting(da, dp);
    int ans = 0;
    rip(i,N,0) {
        chmax(ans, dp[i].dp.back());
    }
    cout << ans << endl;
}
0