Submission #388622

#	Time	Username	Problem	Language	Result	Execution time	Memory
388622		denkendoemeer	Construction of Highway (JOI18_construction)	C++14	100 / 100	257 ms	5460 KiB

construction

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[100005],ch[100005][2],dep[100005],val[100005],f[100005],n;
bool root(int nod)
{
    if (nod!=ch[t[nod]][0] && nod!=ch[t[nod]][1])
        return 1;
    return 0;
}
bool ok(int nod)
{
    if (nod==ch[t[nod]][1])
        return 1;
    return 0;
}
void calc(int nod)
{
    int x=t[nod],y=t[x],oki=ok(nod);
    if (root(x)==0)
        ch[y][ok(x)]=nod;
    t[nod]=y;
    t[ch[x][oki]=ch[nod][!oki]]=x;
    t[ch[nod][!oki]=x]=nod;
}
void mov(int nod)
{
    while(!root(nod)){
        if (!root(t[nod]))
            if (ok(nod)==ok(t[nod]))
                calc(t[nod]);
            else
                calc(nod);
        calc(nod);
    }
}
ll solve(int nod)
{
    vector<tuple<int,int,int>>g;
    int nod2=0;
    for(;nod;nod2=nod,nod=t[nod2]){
        mov(nod);
        int x=ch[nod][1];
        ch[nod][1]=nod2;
        while(ch[nod][0])
            nod=ch[nod][0];
        mov(nod);
        if (x){
            while(ch[x][0])
                x=ch[x][0];
            mov(x);
            val[x]=val[nod];
        }
        if (nod2){
            g.emplace_back(val[nod],dep[nod]+1,dep[nod2]-dep[nod]);
        }
    }
    ll cost=0;
    sort(g.begin(),g.end());
    reverse(g.begin(),g.end());
    for(auto it:g){
        int p,x;
        tie(ignore,p,x)=it;
        int i;
        for(i=p;i>0;i=i-(i&-i))
            cost+=1LL*f[i]*x;
        for(i=p;i<=n;i+=i&(-i))
            f[i]+=x;
    }
    for(auto it:g){
        int p,x;
        tie(ignore,p,x)=it;
        int i;
        for(i=p;i<=n;i+=i&(-i))
            f[i]-=x;
    }
    return cost;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
        scanf("%d",&val[i]);
    int x,y;
    for(i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        dep[y]=dep[x]+1;
        t[y]=x;
        printf("%lld\n",solve(y));
        val[1]=val[y];
    }
return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void mov(int)':
construction.cpp:29:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   29 |         if (!root(t[nod]))
      |            ^
construction.cpp: In function 'int main()':
construction.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
construction.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |         scanf("%d",&val[i]);
      |         ~~~~~^~~~~~~~~~~~~~
construction.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84