제출 #398528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398528		model_code	Arboras (RMI20_arboras)	C++17	100 / 100	4265 ms	19200 KiB

arboras

/**
* user:  perju-verzotti-712
* fname: Luca
* lname: Perju-Verzotti
* task:  Arboras
* score: 100.0
* date:  2020-12-04 11:29:29.204456
*/
#include <bits/stdc++.h>

using namespace std;
const long long mod=1000000007;
long long p[100003],t[100003],sz[100003],depth[100003],heavyhead[100003],heavychild[100003];
vector<long long>v[100003];
long long d[100003];
unsigned long long dp[100003],dp1[100003];
long long bstfiu[100003];
long long pzlin[100003];
long long cnttidk;
long long lsb (long long x)
{
    return x&-x;
}
long long aib[100003];
void update (long long pz, long long val)
{
    for(long long i=pz;i<=100000;i+=lsb(i))
        aib[i]=aib[i]+val;
}
long long query (long long pz)
{
    long long rz=0;
    for(long long i=pz;i>0;i-=lsb(i))
        rz=rz+aib[i];
    return rz;
}
long long s=0;
long long tata (long long pz)
{
    if(t[pz]==0 || t[pz]==pz)
        return pz;
    if(cnttidk>10)
        return tata(t[pz]);
    else
        return t[pz]=tata(t[pz]);
}
void dfsinit (long long pz)
{
    t[pz]=pz;
    sz[pz]=1;
    if(v[pz].size()==0)
        return;
    long long bst=v[pz][0];
    long long b1=-1,b2=-1;
    for(long long i=0;i<v[pz].size();++i)
    {
        depth[v[pz][i]]=1+depth[pz];
        dfsinit(v[pz][i]);
        sz[pz]+=sz[v[pz][i]];
        if(sz[v[pz][i]]>sz[bst])
            bst=v[pz][i];
        unsigned long long dpc=dp[v[pz][i]]+d[v[pz][i]];
        if(b1==-1 || dpc>dp[b1]+d[b1])
        {
            b2=b1;
            b1=v[pz][i];
        }
        else if(b2==-1 || dpc>dp[b2]+d[b2])
            b2=v[pz][i];
    }
    dp[pz]=dp[b1]+d[b1];
    if(b2!=-1)
        dp1[pz]=dp[b2]+d[b2];
    t[b1]=pz;
    bstfiu[pz]=b1;
    s=(s+dp[pz])%mod;
    s=(s+dp1[pz])%mod;
    heavychild[pz]=bst;
}
void dfsinit1 (long long pz)
{
    if(heavychild[p[pz]]==pz)
        heavyhead[pz]=heavyhead[p[pz]];
    else
    {
        heavyhead[pz]=pz;
        ++cnttidk;
    }
    for(long long i=0;i<v[pz].size();++i)
        dfsinit1(v[pz][i]);
}
long long tmpc=0;
void dfsinit2 (long long pz)
{
    pzlin[pz]=++tmpc;
    if(heavychild[pz])
        dfsinit2(heavychild[pz]);
    for(long long i=0;i<v[pz].size();++i)
    {
        if(v[pz][i]==heavychild[pz])
            continue;
        dfsinit2(v[pz][i]);
    }
}
void updatelin (long long a, long long b, long long val)
{
    if(depth[a]>depth[b])
        return;
    s=(s+val%mod*1LL*(depth[b]-depth[a]+1)%mod)%mod;
    while(heavyhead[b]!=heavyhead[a])
    {
        update(pzlin[heavyhead[b]],val);
        update(pzlin[b]+1,-val);
        b=p[heavyhead[b]];
    }
    if(heavyhead[a]==heavyhead[b])
    {
        update(pzlin[a],val);
        update(pzlin[b]+1,-val);
        return;
    }
}
void jegupdate (long long pz, long long val)
{
    d[pz]+=val;
    long long pzc=pz;
    while(1)
    {
        long long tc=tata(pzc);
        long long ptc=p[tc];
        if(p[pzc])
            updatelin(tc,p[pzc],val);
        if(tc==1)
            break;
        pzc=tc;
        long long dpc=query(pzlin[pzc]);
        long long dpt=query(pzlin[ptc]);
        if(dpc+d[pzc]>dpt)
        {
            t[bstfiu[ptc]]=bstfiu[ptc];
            bstfiu[ptc]=pzc;
            t[pzc]=ptc;
            val=dpc+d[pzc]-dpt;
            s=(s+dpt-dp1[ptc])%mod;
            dp1[ptc]=dpt;
           // update(pzlin[ptc],val);
           // s=(s+val)%mod;
        }
        else
        {
            if(dpc+d[pzc]>dp1[ptc])
            {
                s=(s+dpc+d[pzc]-dp1[ptc])%mod;
                dp1[ptc]=dpc+d[pzc];
            }
            break;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    long long n,i,j;
    cin>>n;
    for(i=2;i<=n;++i)
    {
        cin>>p[i];
        ++p[i];
        v[p[i]].push_back(i);
    }
    for(i=2;i<=n;++i)
        cin>>d[i];
    depth[1]=1;
    dfsinit(1);
    dfsinit1(1);
    dfsinit2(1);
    /*if(cnttidk<=10)
    {
        i/=0;
        ++p[-100];
        return 0;
    }*/
    for(i=1;i<=n;++i)
    {
        update(pzlin[i],dp[i]);
        update(pzlin[i]+1,-dp[i]);
    }
    long long q;
    cin>>q;
    cout<<s<<'\n';
    for(i=1;i<=q;++i)
    {
        long long a,b;
        cin>>a>>b;
        ++a;
        jegupdate(a,b);
        cout<<s<<'\n';
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

arboras.cpp: In function 'void dfsinit(long long int)':
arboras.cpp:55:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(long long i=0;i<v[pz].size();++i)
      |                       ~^~~~~~~~~~~~~
arboras.cpp: In function 'void dfsinit1(long long int)':
arboras.cpp:89:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(long long i=0;i<v[pz].size();++i)
      |                       ~^~~~~~~~~~~~~
arboras.cpp: In function 'void dfsinit2(long long int)':
arboras.cpp:98:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(long long i=0;i<v[pz].size();++i)
      |                       ~^~~~~~~~~~~~~
arboras.cpp: In function 'void jegupdate(long long int, long long int)':
arboras.cpp:151:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  151 |             if(dpc+d[pzc]>dp1[ptc])
      |                ~~~~~~~~~~^~~~~~~~~
arboras.cpp: In function 'int main()':
arboras.cpp:163:19: warning: unused variable 'j' [-Wunused-variable]
  163 |     long long n,i,j;
      |                   ^

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45