Submission #1268039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268039		minhpk	Grapevine (NOI22_grapevine)	C++20	53 / 100	855 ms	467780 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=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,min1,val,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;

        f[cen][id*2].min1+=f[cen][id].lazy;
        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;
        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][21];
int fin[100005][21];
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;
    f[cen].resize(4*sz+50);
//    cerr << cen << " " << 4*sz << "\n";
    for (int j=1;j<=4*sz;j++){
         f[cen][j].min1=1e15;
    }
//    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 val=f[p][1].min1+get(p,1,1,sz1[p],sta[x][high[p]]);
                  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 << " ";
                  update1(p,1,1,sz1[p],sta[x][high[p]]);
                  p=par[p];
             }
//             cerr << "\n";
         }else{
             int x,y,t;
             cin >> x >> y >> t;
             if (del[x]>del[y]){
                 swap(x,y);
             }
             int p=x;
             int sadge=m[x][y];
             int val=t-m[x][y];
             while (p!=0){
                  if (sta[x][high[p]]<sta[y][high[p]]){
                      swap(x,y);
                  }
                  update(p,1,1,sz1[p],sta[x][high[p]],fin[x][high[p]],val);
                  p=par[p];
             }
             m[x][y]=m[y][x]=t;
         }
    }
    return 0;
}

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