Submission #1126475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126475		_rain_	Grapevine (NOI22_grapevine)	C++20	100 / 100	1413 ms	189096 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>ii;
#define fi first 
#define se second
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

#define N 1'00'000
#define MAXL 16
const LL INF=(LL)1e18;
vector<int>ke[N+2];
void add_canh(int u,int v){
    ke[u].push_back(v),ke[v].push_back(u);
    return;
}
int n,q;
int u[N+2],v[N+2],w[N+2]={};
bool ap[N+2]={};

class IT{
    public:
    #define lef(id) id*2
    #define rig(id) id*2+1
        vector<LL>st,lz,mn;
        void init(int n){
            st.assign(n*4+2,0),lz.assign(n*4+2,0),mn.assign(n*4+2,INF);
            return;
        }
        void pushdown(int id){
            LL &t=lz[id];
            st[lef(id)]+=t,lz[lef(id)]+=t;
            if (mn[lef(id)]!=INF) mn[lef(id)]+=t;
            st[rig(id)]+=t,lz[rig(id)]+=t;
            if (mn[rig(id)]!=INF) mn[rig(id)]+=t;
            t=0;
            return;
        }
        void modify(int id,int l,int r,int u,int v,int val){
            if (l>v||r<u) return;
            if (u<=l&&r<=v){
                st[id]+=val;
                lz[id]+=val;
                if (mn[id]!=INF) mn[id]+=val;
                return;
            }
            int m=l+r>>1;
            pushdown(id);
            modify(lef(id),l,m,u,v,val);
            modify(rig(id),m+1,r,u,v,val);
            st[id]=min(st[lef(id)],st[rig(id)]);
            mn[id]=min(mn[lef(id)],mn[rig(id)]);
        }
        void soak(int id,int l,int r,int p,int t){
            if (l>p||r<p) return;
            if (l==r) {
                mn[id]=(t?st[id]:INF);
            }
            else{
                int m=(l+r)>>1;
                pushdown(id);
                soak(lef(id),l,m,p,t);
                soak(rig(id),m+1,r,p,t);
                st[id]=min(st[lef(id)],st[rig(id)]);
                mn[id]=min(mn[lef(id)],mn[rig(id)]);
            }
        }
        LL Get(int id,int l,int r,int u,int v){
            if (l>v||r<u) return INF;
            if (u<=l&&r<=v) return st[id];
            int m=l+r>>1;
            pushdown(id);
            return min(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
        }
};
IT st[N+2];
map<pair<int,int>,int>mp;

namespace Centroid{
    int sub[N+2]={},up[N+2]={},dep[N+2]={},sta[MAXL+2][N+2]={},fin[MAXL+2][N+2]={},times[N+2];
    int sz=0;
    bool del[N+2]={};

    void dfs_size(int u,int p){
        sub[u]=1;
        for(auto&v:ke[u]){
            if (v==p||del[v]) continue;
            dfs_size(v,u);
            sub[u]+=sub[v];
        }
        return;
    }
    
    int Find_centroid(int u,int p,int half){
        for(auto&v:ke[u]) {
            if (v==p||del[v]) continue;
            if (sub[v]>half) return Find_centroid(v,u,half);
        }
        return u;
    }

    void dfs(int layer,int root,int u,int p){
        sta[layer][u]=++times[root];
        // if (root==1){
        //     cout<<"(DEBUG)\n";
        //     cout<<u<<' '<<p<<'\n';
        //     cout<<"(END - DEBUG)\n";
        // }
        for(auto&v:ke[u]){
            if (v==p||del[v]) continue;
            dfs(layer,root,v,u);
        }
        fin[layer][u]=times[root];
        return;
    }

    void build_centroid(int u,int p){
        dfs_size(u,u); u=Find_centroid(u,u,sub[u]/2);
        dep[u]=dep[p]+1; up[u]=p;
        dfs(dep[u],u,u,u);
        // cout<<u<<' '<<p<<'\n';
        st[u].init(times[u]);
        del[u]=true;;
        for(auto&v:ke[u]) {
            if (!del[v]) build_centroid(v,u);
        }
        return;
    }
    void anneal(int u,int v,int w){
        if (u>v) swap(u,v);
        int change=w-mp[{u,v}]; mp[{u,v}]=w;
        // cout<<change<<'\n';
        if (dep[u]>dep[v]) swap(u,v);
        int node=u;
        while (node!=0){
            if (sta[dep[node]][u]>sta[dep[node]][v]) swap(u,v);
            st[node].modify(1,1,times[node],sta[dep[node]][v],fin[dep[node]][v],change);
            node=up[node];
        }
        return;
    }
    void soaking(int u,int t){
        int node=u;
        while(node!=0){
            st[node].soak(1,1,times[node],sta[dep[node]][u],t);
            node=up[node];
        }
    }
    LL Find(int u){
        LL ans=INF;
        int node=u;
        while (node!=0){
           int k=sta[dep[node]][u];
           ans=min(ans,st[node].Get(1,1,times[node],k,k)+st[node].mn[1]);
           node=up[node];
        }
        return (ans==INF?-1:ans);
    }
}
using namespace Centroid;

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    FOR(i,1,n-1){
        cin>>u[i]>>v[i]>>w[i];
        add_canh(u[i],v[i]);
    }
    build_centroid(1,0);
    FOR(i,1,n-1) anneal(u[i],v[i],w[i]);
    while(q--){
        int t; cin>>t;
        if (t==1) {
            int x; cin>>x; cout<<Find(x)<<'\n';
        }
        if (t==2){
            int x; cin>>x; 
            ap[x]^=1;
            soaking(x,ap[x]);
        }
        if (t==3){
            int a,b,w; cin>>a>>b>>w; 
            anneal(a,b,w);
        }
    }
    exit(0);
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32