제출 #1328130

#제출 시각아이디문제언어결과실행 시간메모리
1328130model_codeMigration Plan (JOI25_migration)C++20
100 / 100
2704 ms957700 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define REP(i,k,n) for(ll i=(ll)(k); i<(ll)(n); i++)
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

struct Point {
    ll x, y, w;
    Point(ll x_, ll y_, ll w_):x(x_),y(y_),w(w_){}
};
struct BIT{
    vi bit;ll n;
    ll sum(ll i){
        ll res=0;
        for(;i>0;i-=i&-i)res+=bit[i];
        return res;
    }
    BIT(ll n_):n(n_){bit=vi(n+1);}
    void add(ll i,ll x){
        for(i++;i<=n;i+=i&-i)bit[i]+=x;
    }
    ll get(ll a,ll b){
        if(b<=a)return 0ll;
        return sum(b)-sum(a);
    }
};
vi RectangleSum(ll H, ll W, vector<Point> points, vector<pair<P,P>> queries) {
    vi ans(queries.size());
    vector<vp> event(H+1);
    rep(i,queries.size()){
        event[queries[i].first.first].pb(0,i);
        event[queries[i].first.second].pb(1,i);
    }
    rep(i,points.size())event[points[i].x].pb(2,i);
    BIT bit(W);
    rep(i,H+1)for(auto x:event[i]){
        if(x.first == 0)ans[x.second] -= bit.get(queries[x.second].second.first, queries[x.second].second.second);
        if(x.first == 1)ans[x.second] += bit.get(queries[x.second].second.first, queries[x.second].second.second);
        if(x.first == 2)bit.add(points[x.second].y, points[x.second].w);
    }
    return ans;
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll N, D = 0, M = 0; cin>>N;
    vvi g1(N);
    vi dep1(N);
    REP(i,1,N){
        ll a;cin>>a;a--;g1[a].pb(i);
    }
    ll cnt1=0;
    vp euler1(N);
    auto dfs1=[&](auto && self, ll i, ll p, ll d) -> void {
        euler1[i].first = cnt1++;
        dep1[i] = d;
        for(ll x:g1[i]) self(self,x,i,d+1);
        euler1[i].second = cnt1;
    };dfs1(dfs1,0,-1,0);
    for(ll x:dep1)chmax(D, x+1);
    vi v(N);rep(i,N)cin>>v[i];
    ll Q; cin>>Q;
    vvi query(Q,vi(3));
    rep(i,Q){
        cin>>query[i][0]>>query[i][1];
        if(query[i][0]!=1)query[i][1]--;
        if(query[i][0]!=3)cin>>query[i][2];
        if(query[i][0]==2)M++;
    }
    M += D;
    vvi g2(M+1);
    vi par2(M,-1),rlabel(D);
    ll cm=D;
    rep(i,D)rlabel[i]=i;
    vp event(Q,P(-1,-1));
    rep(i,Q){
        if(query[i][0]==1){
            ll X=query[i][1],Y=query[i][2];
            if(X>=D||rlabel[X]==-1)continue;
            if(rlabel[Y]==-1){
                rlabel[Y]=rlabel[X];
                rlabel[X]=-1;
            } else{
                par2[rlabel[X]]=rlabel[Y];
                g2[rlabel[Y]].pb(rlabel[X]);
                event[i]=P(rlabel[Y],rlabel[X]);
                rlabel[X]=-1;
            }
        }
        if(query[i][0]==2){
            ll X=dep1[query[i][1]], Y=cm;
            if(rlabel[X]==-1){
                rlabel[X]=Y;
            } else{
                par2[Y]=rlabel[X];
                g2[rlabel[X]].pb(Y);
                event[i]=P(rlabel[X],Y);
            }
            cm++;
        }
        if(query[i][0]==3){
            ll X=dep1[query[i][1]];
            event[i].first=rlabel[X];
        }
    }
    ll cnt2=0;
    vp euler2(M+1);
    rep(i,M)if(par2[i]==-1)g2[M].pb(i);
    auto dfs2=[&](auto && self, ll i, ll p) -> void {
        euler2[i].first = cnt2++;
        for(ll x:g2[i]) self(self,x,i);
    };dfs2(dfs2,M,-1);
    rep(i,M+1)euler2[i].second=euler2[i].first+1;
    vector<Point> points;
    vector<pair<P,P>> queries;
    rep(i,N)points.pb(euler1[i].first, euler2[dep1[i]].first, v[i]);
    cm = D;
    rep(i,Q){
        if(query[i][0]!=3&&event[i]!=P(-1,-1)){
            euler2[event[i].first].second = euler2[event[i].second].second;
        }
        if(query[i][0]==2){
            points.pb(euler1[query[i][1]].first, euler2[cm].first, query[i][2]);
            cm++;
        }
        if(query[i][0]==3){
            if(event[i].first != -1) queries.pb(euler1[query[i][1]], euler2[event[i].first]);
            else queries.pb(P(0,0),P(0,0));
        }
    }
    vi ans=RectangleSum(N, M+1, points, queries);
    for(ll x:ans) cout << x << '\n';
}
#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...