Submission #1111799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111799		Tai_xiu	Grapevine (NOI22_grapevine)	C++14	100 / 100	1756 ms	279480 KiB

Main

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

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=100005;
const Z oo=1e17;
Z sz[maxn],tin[20][maxn],tout[20][maxn],vis[maxn],id[maxn],n,par[maxn],q,h[maxn],have[maxn];
vi g[maxn];
map<Z,Z>mp[maxn];
Z ew[maxn];
ii canh[maxn];
struct segtree
{
    vi st,lazy;
    segtree(){}
    segtree(Z _n,Z _val){
        st=vi(4*_n+7,_val);
        lazy=vi(4*_n+7);
    }
    void push(Z v)
    {
        st[v*2]+=lazy[v];
        st[v*2+1]+=lazy[v];
        lazy[v*2]+=lazy[v];
        lazy[v*2+1]+=lazy[v];
        lazy[v]=0;
    }
  void update(Z v,Z tl,Z tr,Z l,Z r,Z val)
  {
      if (tl>tr || l>r || tl>r || tr<l) return;
        if (tl>=l && tr<=r){
            st[v]+=val;
            lazy[v]+=val;
            return;
        }
        Z tm=tl+tr>>1;
        push(v);
        update(v*2,tl,tm,l,r,val);
        update(v*2+1,tm+1,tr,l,r,val);
        st[v]=min(st[v*2],st[v*2+1]);
  }
   void change(Z v,Z tl,Z tr,Z pos,Z val)
  {
        if (tl==tr) {
            st[v]=val;
            return;
        }
        push(v);
        Z tm=tl+tr>>1;
        if (pos<=tm) change(v*2,tl,tm,pos,val);
        else change(v*2+1,tm+1,tr,pos,val);
        st[v]=min(st[v*2],st[v*2+1]);
  }
  Z query(Z v,Z tl,Z tr,Z l,Z r)
  {
      if (tl>tr || l>r || tl>r || tr<l) return oo;
      if (tl>=l && tr<=r) return st[v];
      push(v);
      Z tm=(tl+tr)>>1;
      return min(query(v*2,tl,tm,l,r),query(v*2+1,tm+1,tr,l,r));
  }
}st1[maxn],st2[maxn];
Z getsize(Z u,Z p)
{
    sz[u]=1;
//    cout<<u<<endl;
    for (Z v:g[u]){
        if (vis[v] || v==p) continue;
        sz[u]+=getsize(v,u);
    }
    return sz[u];
}
Z centroid (Z u,Z p,Z sai)
{
//    cout<<u<<endl;
    for (Z v:g[u]){
        if (sz[v]>sai/2 && !vis[v] && v!=p) return centroid(v,u,sai);
    }
    return u;
}
void dfs(Z u,Z p,Z depth,Z root)
{
    tin[depth][u]=++id[root];
    for (Z v:g[u]){
        if (v!=p && !vis[v]) dfs(v,u,depth,root);
    }
    tout[depth][u]=id[root];
}
void decomp(Z u,Z p,Z depth)
{
    Z c=centroid(u,u,getsize(u,u));
    vis[c]=1;
    par[c]=p;
    st1[c]=segtree(sz[u],0);
    st2[c]=segtree(sz[u],oo);
    h[c]=depth;
//    cout<<c<<" "<<depth<<'\n';
    dfs(c,-1,depth,c);
    for (Z v:g[c]) if (!vis[v]) decomp(v,c,depth+1);
}
void anneal(Z u,Z v,Z w)
{
    if (h[u]>h[v]) swap(u,v);
    Z node=u;
    REP(i,h[u],0){
        Z curr=(tin[i][u]<tin[i][v])?v:u;
        st1[node].update(1,1,id[node],tin[i][curr],tout[i][curr],w);
        st2[node].update(1,1,id[node],tin[i][curr],tout[i][curr],w);
        node=par[node];
    }
}
void soak(Z u)
{
    have[u]^=1;
    Z node=u;
    REP(i,h[u],0){
//        cout<<node<<" "<<" "<<st1[node].query(1,1,id[node],tin[i][u],tin[i][u])<<" ??\n";

        if (!have[u]) st2[node].change(1,1,id[node],tin[i][u],oo);
        else st2[node].change(1,1,id[node],tin[i][u],st1[node].query(1,1,id[node],tin[i][u],tin[i][u]));
        node=par[node];
    }
}
void seek(Z u)
{
    Z ans=oo;
    Z node=u;
    REP(i,h[u],0){
       ans=min(ans,st1[node].query(1,1,id[node],tin[i][u],tin[i][u])+st2[node].st[1]);
       node=par[node];
    }
    if (ans>=1e14) cout<<-1<<'\n';
    else cout<<ans<<'\n';
}
/*
7 2
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 3
1 1


*/
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    FOR(i,1,n-1){
        cin>>canh[i].first>>canh[i].second>>ew[i];
        if (canh[i].first>canh[i].second) swap(canh[i].first,canh[i].second);
        mp[canh[i].first][canh[i].second]=i;
        g[canh[i].first].pb(canh[i].second);
        g[canh[i].second].pb(canh[i].first);

    }
    decomp(1,-1,0);
    FOR(i,1,n-1)
    {
        anneal(canh[i].first,canh[i].second,ew[mp[canh[i].first][canh[i].second]]);
    }
    while(q--){
        Z type;
        cin>>type;
        if (type==1) {
            Z u; cin>>u; seek(u);
        }
        else if (type==2){
            Z u; cin>>u; soak(u);
        }
        else {
            Z u,v,w; cin>>u>>v>>w;
            if (u>v) swap(u,v);
            anneal(u,v,w-ew[mp[u][v]]);
           ew[ mp[u][v]]=w;
        }
    }
//    FOR(i,0,2){
//        FOR(j,1,n) cout<<tin[i][j]<<" ";
//        cout<<'\n';
//        FOR(j,1,n) cout<<tout[i][j]<<" ";
//        cout<<'\n';
//        cout<<"////\n";
//    }
//    FOR(i,1,3) cout<<id[node]<<" ";
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:61:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         Z tm=tl+tr>>1;
      |              ~~^~~
Main.cpp: In member function 'void segtree::change(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:74:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         Z tm=tl+tr>>1;
      |              ~~^~~

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