Submission #646517

#	Time	Username	Problem	Language	Result	Execution time	Memory
646517		danikoynov	Arboras (RMI20_arboras)	C++14	100 / 100	4454 ms	32780 KiB

arboras

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

int n, q;
int heavy[maxn], ch_idx[maxn], ch_pos[maxn], ch_head[maxn];
int par[maxn], depth[maxn], sub[maxn], strong[maxn];
ll dp[maxn][2], dis[maxn];
vector < pair < int, ll > > g[maxn];

void dfs(int v)
{
    heavy[v] = -1;
    strong[v] = -1;
    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == par[v])
            continue;

        depth[nb.first] = depth[v] + 1;
        dfs(nb.first);
        if (heavy[v] == -1 || sub[nb.first] > sub[heavy[v]])
            heavy[v] = nb.first;
        if (dp[nb.first][0] + nb.second >= dp[v][0])
        {
            dp[v][1] = dp[v][0];
            dp[v][0] = dp[nb.first][0] + nb.second;
            strong[v] = nb.first;
        }
        else if (dp[nb.first][0] + nb.second > dp[v][1])
        {
            dp[v][1] = dp[nb.first][0] + nb.second;
        }
    }
}

const int block = 20;
ll ans = 0;
pair < ll, ll > tree[4 * maxn];
ll lazy[4 * maxn], nxt_free, pot[maxn];
struct chain
{
    vector < int > ver;
    vector < pair < ll, ll > > st;
    set < int > weak;
    int ch_root;


    void build_tree(int root, int left, int right)
    {
        if (left == right)
        {
            pot[ver[left]] = ch_root + root;
            tree[ch_root + root] = st[left];
            return;
        }

        int mid = (left + right) / 2;
        build_tree(root * 2, left, mid);
        build_tree(root * 2 + 1, mid + 1, right);

    }


    void build_chain()
    {
        for (int i = 0; i < ver.size(); i ++)
        {
            st.push_back({dp[ver[i]][0], dp[ver[i]][1]});
            if (i != (int)(ver.size()) - 1)
            {
                if (strong[ver[i]] != ver[i + 1])
                    weak.insert(i);
            }
        }
        ch_root = nxt_free;
        nxt_free += ver.size() * 4;
        build_tree(1, 0, (int)st.size() - 1);
    }

    void push_lazy(int root, int left, int right)
    {
        ///if (lazy[root].first == lazy[root].second && lazy[root].first == 0)
        if (left == right)
        {
            tree[root + ch_root].first += lazy[ch_root + root];
        }
        else
        {
            lazy[ch_root + root * 2] += lazy[ch_root + root];
            lazy[ch_root + root * 2 + 1] += lazy[ch_root + root];
        }
        lazy[ch_root + root] = 0;
    }

    pair < ll, ll > get_node(int root, int left, int right, int idx)
    {
        int mid;
        while(true)
        {
            if (lazy[ch_root + root] != 0)
                push_lazy(root, left, right);
            if (left == right)
            {
                return tree[ch_root + root];
            }
            mid = (left + right) / 2;
            if (idx <= mid)
            {
                root = root * 2;
                right = mid;
            }
            else
            {
                root = root * 2 + 1;
                left = mid + 1;
            }
        }
        /**if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);
        if (left == right)
            return tree[ch_root + root];

        int mid = (left + right) / 2;
        if (idx <= mid)
            return get_node(root * 2, left, mid, idx);
        return get_node(root * 2 + 1, mid + 1, right, idx);*/
    }

    void set_node(int root, int left, int right, int idx, pair < ll,ll >  val)
    {
        int mid;
        while(true)
        {
            if (lazy[ch_root + root] != 0)
                push_lazy(root, left, right);
            if (left == right)
            {
                tree[ch_root + root] = val;
                return;
            }
                    mid = (left + right) / 2;
            if (idx <= mid)
            {
                root = root * 2;
                right = mid;
            }
            else
            {
                root = root * 2 + 1;
                left = mid + 1;
            }
        }
        /**if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);
        if (left == right)
        {
            tree[ch_root + root] = val;
            return;
        }

        int mid = (left + right) / 2;
        if (idx <= mid)
            set_node(root * 2, left, mid, idx, val);
        else
            set_node(root * 2 + 1, mid + 1, right, idx, val);*/

    }

    struct sol
    {
        int root, left, right, qleft, qright;
        ll val;

        sol(int _root, int _left, int _right, int _qleft, int _qright, ll _val)
        {
            root = _root;
            left = _left;
            right = _right;
            qleft = _qleft;
            qright = _qright;
            val = _val;
        }
    };
   void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);

        if (left == qleft && right == qright)
        {
            lazy[ch_root + root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        if (qright <= mid)
            update_range(root * 2, left, mid, qleft, qright, val);
        else if (qleft > mid)
            update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
        else
        {
            update_range(root * 2, left, mid, qleft, mid, val);
            update_range(root * 2 + 1, mid + 1, right, mid + 1, qright, val);
        }
        /**if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root + ch_root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;

        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);*/
    }
    pair < ll, ll > get_element(int v)
    {
        if (ver.size() < block)
        return {dp[v][0], dp[v][1]};
        return get_node(1, 0, (int)(ver.size()) - 1, ch_pos[v]);
    }

    void set_element(int v, pair < ll, ll > val)
    {
        if (ver.size() < block)
        {
            dp[v][0] = val.first;
            dp[v][1] = val.second;
            return;
        }
        set_node(1, 0, (int)(ver.size()) - 1, ch_pos[v], val);
    }

    void update_path(int lf, int rf, ll val)
    {
        if (ver.size() < block)
        {
            for (int i = lf; i <= rf; i ++)
                dp[ver[i]][0] += val;
        }
        update_range(1, 0, (int)(ver.size()) - 1, lf, rf, val);
    }

};

vector < chain > ch;

void hld(int v)
{
    ch_pos[v] = ch.back().ver.size();
    ch.back().ver.push_back(v);
    ch_head[v] = ch.back().ver[0];
    ch_idx[v] = (int)(ch.size()) - 1;


    if (heavy[v] != -1)
    {
        hld(heavy[v]);
    }

    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == par[v] || nb.first == heavy[v])
            continue;
        ch.emplace_back();
        hld(nb.first);

    }
}

void update(int v, ll d)
{
    ll cur = dp[v][0];
    dis[v] += d;
    while(true)
    {
        if (v == 0)
            break;
        cur = cur + dis[v];
        ///cout << v << " :: " << cur << endl;
        if (strong[par[v]] == v)
        {
            ans = ans + cur - dp[par[v]][0];
            ans = (ans + mod) % mod;
            dp[par[v]][0] = cur;
            v = par[v];
            continue;
        }

        if (cur <= dp[par[v]][1])
            break;
        if (cur <= dp[par[v]][0])
        {
            ans = ans + cur - dp[par[v]][1];
            ans = (ans + mod) % mod;
            dp[par[v]][1] = cur;
            break;
        }
        ans = ans + cur - dp[par[v]][1];
        ans = (ans + mod) % mod;
        dp[par[v]][1] = dp[par[v]][0];
        dp[par[v]][0] = cur;
        strong[par[v]] = v;
        v = par[v];
    }

    /**cout << "------------" << endl;
    for (int i = 0; i < n; i ++)
        cout << dp[i][0] << " " << dp[i][1] << endl;
    cout << "------------" << endl;*/
}

void update_edge(int v, ll d)
{
    dis[v] += d;
    pair < ll, ll > cur, aft;
    set < int > :: iterator it;
    cur = ch[ch_idx[v]].get_element(v);
    while(true)
    {
        ///cout << "here " << v << endl;
        if (v == 0)
            break;
        if (ch_head[v] == v)
        {
            ///cur = ch[ch_idx[v]].get_element(v);
            aft = ch[ch_idx[par[v]]].get_element(par[v]);
            if (strong[par[v]] == v)
            {
                ans = (ans + cur.first + dis[v] - aft.first) % mod;
                aft.first = cur.first + dis[v];
                ch[ch_idx[par[v]]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
            }
            else
            {

                if (cur.first + dis[v] <= aft.second)
                    break;
                if (cur.first + dis[v] <= aft.first)
                {
                    ans = (ans + cur.first + dis[v] - aft.second) % mod;
                    aft.second = cur.first + dis[v];
                    ch[ch_idx[par[v]]].set_element(par[v], aft);
                    break;
                }

                ans = (ans + cur.first + dis[v] - aft.second) % mod;

                if (strong[par[v]] == ch[ch_idx[par[v]]].ver[ch_pos[par[v]] + 1])
                    ch[ch_idx[par[v]]].weak.insert(ch_pos[par[v]]);
                strong[par[v]] = v;

                aft.second = aft.first;
                aft.first = cur.first + dis[v];
                ch[ch_idx[par[v]]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
                continue;
            }
        }
        else
        {
            int pos = 0;
            if (!ch[ch_idx[v]].weak.empty())
            {
                it = ch[ch_idx[v]].weak.lower_bound(ch_pos[v]);
                if (it != ch[ch_idx[v]].weak.begin())
                {
                    it = prev(it);
                    pos = *it + 1;
                }
            }
            /**for (int x : ch[ch_idx[v]].weak)
                cout << x << " ";
            cout << endl;*/
            ///cout << pos << " " << ch_pos[v] << endl;
            if (pos == ch_pos[v])
            {

                ///cur = ch[ch_idx[v]].get_element(v);
                aft = ch[ch_idx[par[v]]].get_element(par[v]);
                if (cur.first + dis[v] <= aft.second)
                    break;
                if (cur.first + dis[v] <= aft.first)
                {
                    ans = (ans + cur.first + dis[v] - aft.second) % mod;
                    aft.second = cur.first + dis[v];
                    ch[ch_idx[par[v]]].set_element(par[v], aft);
                    break;
                }

                strong[par[v]] = v;
                ch[ch_idx[v]].weak.erase(pos - 1);
                ans = (ans + cur.first + dis[v] - aft.second) % mod;
                aft.second = aft.first;
                aft.first = cur.first + dis[v];
                ch[ch_idx[v]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
                continue;

            }
            else
            {
                ///cur = ch[ch_idx[v]].get_element(v);
                aft = ch[ch_idx[par[v]]].get_element(par[v]);
                ll diff = cur.first + dis[v] - aft.first;
                ans = (ans + diff * (ch_pos[v] - pos)) % mod;
                ch[ch_idx[v]].update_path(pos, ch_pos[v] - 1, diff);
                v = ch[ch_idx[v]].ver[pos];
                cur = ch[ch_idx[v]].get_element(v);
                continue;
            }
        }
    }
}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
        cin >> par[i];
    for (int i = 1; i < n; i ++)
    {
        cin >> dis[i];
        g[par[i]].push_back({i, dis[i]});
    }

    par[0] = -1;
    dfs(0);
    ch.emplace_back();
    hld(0);

    /**for (int i = 0; i < ch.size(); i ++)
    {
        cout << i << " : ";
        for (int v : ch[i].ver)
            cout << v << " ";
        cout << endl;
    }*/

    for (int i = 0; i < ch.size(); i ++)
        ch[i].build_chain();

    for (int i = 0; i < ch.size(); i ++)
    {
        for (int j = 0; j < (int)ch[i].ver.size() - 1; j ++)
        {
            if (strong[ch[i].ver[j]] != ch[i].ver[j + 1])
                ch[i].weak.insert(j);
        }
    }

    cin >> q;
    for (int i = 0; i < n; i ++)
        ans = (ans + dp[i][0] + dp[i][1]) % mod;
    cout << ans << endl;
    for (int i = 0; i < q; i ++)
    {
        ///if (i % 10000 == 0)
           // cout << "YEP" << endl;
        int v;
        ll d;
        cin >> v >> d;
        ///update(v, d);
        update_edge(v, d);
        cout << ans << endl;
    }
}

int main()
{
    ///freopen("input.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

arboras.cpp: In member function 'void chain::build_chain()':
arboras.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < ver.size(); i ++)
      |                         ~~^~~~~~~~~~~~
arboras.cpp: In function 'void solve()':
arboras.cpp:469:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  469 |     for (int i = 0; i < ch.size(); i ++)
      |                     ~~^~~~~~~~~~~
arboras.cpp:472:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  472 |     for (int i = 0; i < ch.size(); i ++)
      |                     ~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45