Submission #1268041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268041		uzukishinobu	Grapevine (NOI22_grapevine)	C++20	100 / 100	909 ms	536324 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
vector<pair<int,int>> z[1000005];
int high[1000005];
int child[100005];
int sz;
int par[1000005];
int del[1000005];
int sz1[1000005];
int inf= (int)1e15;

void predfs(int i,int parent){
     child[i]=1;
     for (auto [p,w]:z[i]){
          if (p==parent || del[p]){
              continue;
          }
          predfs(p,i);
          child[i]+=child[p];
     }
}

int centroid(int i,int parent){
   for (auto [p,w]:z[i]){
        if (p==parent || del[p]){
            continue;
        }
        if (child[p]>sz/2){
            return centroid(p,i);
        }
   }
   return i;
}
struct node{
      int cur;
      int min1;
      int val;
      int lazy;
};
int cur;
vector <node> f[100005];
void push(int id,int cen){
    if (f[cen][id].lazy!=0){
        f[cen][id*2].lazy+=f[cen][id].lazy;
        f[cen][id*2+1].lazy+=f[cen][id].lazy;

        f[cen][id*2].val+=f[cen][id].lazy;
        f[cen][id*2+1].val+=f[cen][id].lazy;

        if (f[cen][id*2].min1 < inf) f[cen][id*2].min1 += f[cen][id].lazy;
        if (f[cen][id*2+1].min1 < inf) f[cen][id*2+1].min1 += f[cen][id].lazy;

        f[cen][id].lazy=0;
    }
}
void update(int cen,int id,int l,int r,int x,int y,int val){
    if (x>r || y<l){
        return;
    }
    if (l>=x && y>=r){
        f[cen][id].val+=val;
        if (f[cen][id].min1 < inf) f[cen][id].min1+=val;
        f[cen][id].lazy+=val;
        return;
    }
    int mid=(l+r)/2;
    push(id,cen);
    update(cen,id*2,l,mid,x,y,val);
    update(cen,id*2+1,mid+1,r,x,y,val);
    f[cen][id].min1=min(f[cen][id*2].min1,f[cen][id*2+1].min1);
}

void update1(int cen,int id,int l,int r,int pos){
     if (l==r){
         f[cen][id].cur^=1;
         if (f[cen][id].cur){
             f[cen][id].min1=f[cen][id].val;
         }else{
             f[cen][id].min1=inf;
         }
         return;
     }
     int mid=(l+r)/2;
     push(id,cen);
     if (pos<=mid){
         update1(cen,id*2,l,mid,pos);
     }else{
         update1(cen,id*2+1,mid+1,r,pos);
     }
     f[cen][id].min1=min(f[cen][id*2].min1,f[cen][id*2+1].min1);
}

int get(int cen,int id,int l,int r,int pos){
    if (l==r){
        return f[cen][id].val;
    }
    int mid=(l+r)/2;
    push(id,cen);
    if (pos<=mid){
        return get(cen,id*2,l,mid,pos);
    }else{
        return get(cen,id*2+1,mid+1,r,pos);
    }
}

int sta[100005][55];
int fin[100005][55];
int tour;
unordered_map<int,int> m[1000005];

void dfs(int i,int parent,int val,int cen){
     tour++;
     sta[i][high[cen]]=tour;
     update(cen,1,1,sz1[cen],sta[i][high[cen]],sta[i][high[cen]],val);
     for (auto [p,w]:z[i]){
          if (p==parent || del[p]){
              continue;
          }
          dfs(p,i,val+w,cen);
     }
     fin[i][high[cen]]=tour;
}

void decompose(int i,int parent){

    predfs(i,0);
    sz=child[i];
    int cen=centroid(i,0);
//    cerr << cen << "\n";
    sz1[cen]=sz;
    high[cen]=high[parent]+1;
    par[cen]=parent;
    int SZ = 4*sz + 50;
    f[cen].assign(SZ+5, {0, (int)inf, 0, 0});
    for (int j=1;j<=4*sz+2;j++){
         f[cen][j].min1=inf;
         f[cen][j].val=0;
         f[cen][j].lazy=0;
         f[cen][j].cur=0;
    }
//    cerr << cen << "\n";
    cur++;
    del[cen]=cur;
    tour=0;
    dfs(cen,cen,0,cen);
    for (auto [p,w]:z[cen]){
         if (p==parent || del[p]){
             continue;
         }
//         cerr << p << " ";
         decompose(p,cen);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<a;i++){
         int x,y,t;
         cin >> x >> y >> t;
         z[x].push_back({y,t});
         z[y].push_back({x,t});
         m[x][y]=t;
         m[y][x]=t;
    }
    decompose(1,0);

//    for (int i=1;i<=a;i++){
//         cerr << par[i] << " ";
//    }
//    cerr << "\n";
    while (b--){
         int c;
         cin >> c;
         if (c==1){
             int x;
             cin >> x;
             int p=x;
             int res=inf;
             while (p!=0){
                  int pos = sta[x][high[p]];
                  if (pos==0){ p=par[p]; continue; }
                  int val=f[p][1].min1 + get(p,1,1,sz1[p], pos);
                  res=min(res,val);
                  p=par[p];
             }
             if (res==inf){
                 cout << -1 << "\n";
             }else{
                 cout << res << "\n";
             }
         }else if (c==2){
             int x;
             cin >> x;
             int p=x;
             while (p!=0){
 //                 cerr << p << " ";
                  int pos = sta[x][high[p]];
                  if (pos!=0) update1(p,1,1,sz1[p],pos);
                  p=par[p];
             }
//             cerr << "\n";
         }else{
             int x,y,t;
             cin >> x >> y >> t;
             int ox = x, oy = y;
             int u0 = ox, v0 = oy;
             if (del[u0] > del[v0]) swap(u0, v0);
             int oldw = 0;
             if (m[u0].find(v0) != m[u0].end()) oldw = m[u0][v0];
             int delta = t - oldw;
             int p = u0;
             while (p!=0){
                  int u = u0, v = v0;
                  int pos_u = sta[u][high[p]];
                  int pos_v = sta[v][high[p]];
                  if (pos_u==0 || pos_v==0){
                      p = par[p];
                      continue;
                  }
                  if (pos_u < pos_v) swap(u,v), swap(pos_u,pos_v);
                  update(p,1,1,sz1[p], pos_u, fin[u][high[p]], delta);
                  p=par[p];
             }
             m[ox][oy]=m[oy][ox]=t;
         }
    }
    return 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