Submission #1369700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369700		12345678	Migration Plan (JOI25_migration)	C++20	12 / 100	7604 ms	540544 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5, kx=21;

int n, pa[nx][kx], lvl[nx], q, t, x, y, sz[nx];
vector<int> adj[nx];
map<int, int> mp[nx];

void dfs(int u)
{
    if (u!=1) lvl[u]=lvl[pa[u][0]]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:adj[u]) dfs(v);
}

int getnode(int u, int tg)
{
    for (int i=kx-1; i>=0; i--) if (lvl[pa[u][i]]>=tg) u=pa[u][i];
    return u;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=2; i<=n; i++) cin>>pa[i][0], adj[pa[i][0]].push_back(i);
    lvl[0]=-1;
    dfs(1);
    for (int i=1; i<=n; i++) cin>>sz[i], mp[lvl[i]][i]=sz[i];
    cin>>q;
    while (q--)
    {
        cin>>t;
        if (t==1)
        {
            cin>>x>>y;
            for (auto [u, cnt]:mp[x])
            {
                int v=getnode(u, y);
                mp[y][v]+=cnt;
            }
            mp[x].clear();
        }
        if (t==2)
        {
            cin>>x>>y;
            mp[lvl[x]][x]+=y;
        }
        if (t==3)
        {
            cin>>x;
            cout<<mp[lvl[x]][x]<<'\n';
        }
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 4 / 4
• Subtask 3: 8 / 8
• Subtask 4: 0 / 13
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15
• Subtask 7: 0 / 27
• Subtask 8: 0 / 18