Submission #1340264

#TimeUsernameProblemLanguageResultExecution timeMemory
1340264alexddMigration Plan (JOI25_migration)C++20
100 / 100
6454 ms447300 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;

int n, timer;
int val[MAXN], tin[MAXN], tout[MAXN], depth[MAXN], parent[MAXN];
vector<int> con[MAXN];

struct GROUP
{
    map<int,int> fr;
    void init(vector<int> nodes)
    {
        for(int x:nodes)
            fr[tin[x]] += val[x];
    }
    void reset()
    {
        fr.clear();
    }
};
GROUP comp[MAXN];

void merge(int idx, int idy)
{
    assert(idx < idy);
    if(comp[idx].fr.size() < comp[idy].fr.size())
    {
        swap(comp[idx], comp[idy]);
    }
    for(auto it:comp[idy].fr)
    {
        if(it.second)
            comp[idx].fr[it.first] += it.second;
    }
    comp[idy].reset();
}
int query(int id, int le, int ri)
{
    auto it = comp[id].fr.lower_bound(le);
    int sum = 0;
    while(it != comp[id].fr.end() && (*it).first <= ri)
    {
        sum = sum + (*it).second;
        it = comp[id].fr.erase(it);
    }
    if(sum) comp[id].fr[le] += sum;
    return sum;
}

void dfs(int nod)
{
    tin[nod] = ++timer;
    for(int adj:con[nod])
    {
        depth[adj] = depth[nod] + 1;
        dfs(adj);
    }
    tout[nod] = timer;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>parent[i];
        con[parent[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        comp[depth[i]].fr[tin[i]] += val[i];
    }
    int q;
    cin>>q;
    while(q--)
    {
        int tip;
        cin>>tip;
        if(tip == 1)
        {
            int x,y;
            cin>>x>>y;
            merge(y, x);
        }
        else if(tip == 2)
        {
            int a, newv;
            cin>>a>>newv;
            comp[depth[a]].fr[tin[a]] += newv;
        }
        else
        {
            assert(tip == 3);
            int b;
            cin>>b;
            cout<<query(depth[b], tin[b], tout[b])<<"\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...