Submission #281586

#	Time	Username	Problem	Language	Result	Execution time	Memory
281586		MKopchev	Construction of Highway (JOI18_construction)	C++14	100 / 100	748 ms	29416 KiB

construction

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,inp[nmax],help[nmax];

void compress()
{
    for(int i=1;i<=n;i++)help[i]=inp[i];
    sort(help+1,help+n+1);

    for(int i=1;i<=n;i++)
    {
        inp[i]=lower_bound(help+1,help+n+1,inp[i])-help;
    }
}

pair<int,int> edges[nmax];

vector<int> adj[nmax];

int parent[nmax];

int heaviest[nmax];

int SZ[nmax];

void dfs(int node,int par)
{
    SZ[node]=1;
    parent[node]=par;

    for(auto k:adj[node])
        if(k!=par)
        {
            dfs(k,node);
            SZ[node]+=SZ[k];

            if(SZ[k]>SZ[heaviest[node]])heaviest[node]=k;
        }

}

struct info
{
    int mini,maxi,lazy;
};

vector< int > path[nmax];

vector< info > tree[nmax];

void push(int id,int node)
{
    if(tree[id][node].lazy!=-1)
    {
        tree[id][node*2].lazy=tree[id][node].lazy;
        tree[id][node*2+1].lazy=tree[id][node].lazy;
    }
    tree[id][node].lazy=-1;
}

info actual(info ret)
{
    if(ret.lazy!=-1)
    {
        ret.mini=ret.lazy;
        ret.maxi=ret.lazy;
    }
    ret.lazy=-1;
    return ret;
}
info my_merge(info l,info r)
{
    l=actual(l);
    r=actual(r);

    info ret;
    ret.lazy=-1;
    ret.mini=min(l.mini,r.mini);
    ret.maxi=max(l.maxi,r.maxi);
    return ret;
}
void update(int id,int node,int l,int r,int lq,int rq,int val)
{
    //cout<<"update "<<id<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<" "<<val<<endl;

    if(l==lq&&r==rq)
    {
        tree[id][node].lazy=val;
        return;
    }

    push(id,node);

    int av=(l+r)/2;

    if(lq<=av)update(id,node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update(id,node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
}

int query(int id,int node,int l,int r,int pos)
{
    if(l==r)return actual(tree[id][node]).mini;

    push(id,node);

    int av=(l+r)/2,mem;

    if(pos<=av)mem=query(id,node*2,l,av,pos);
    else mem=query(id,node*2+1,av+1,r,pos);

    tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
    return mem;
}

int query_range(int id,int node,int l,int r,int lq,int rq,int val)
{
    //cout<<"query_range "<<id<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<" "<<val<<" "<<tree[id][node].lazy<<" "<<tree[id][node].mini<<" "<<tree[id][node].maxi<<endl;

    if(tree[id][node].lazy!=-1)
    {
        //cout<<"go go "<<lq<<" "<<rq<<" "<<tree[id][node].lazy<<endl;

        if(tree[id][node].lazy==val)return lq;
        return rq+1;
    }

    if(tree[id][node].maxi<val||tree[id][node].mini>val)return rq+1;

    push(id,node);

    int av=(l+r)/2;

    if(av<rq)
    {
        int mem=query_range(id,node*2+1,av+1,r,max(lq,av+1),rq,val);

        if(mem!=max(lq,av+1))
        {
            tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
            return mem;
        }
    }

    if(lq<=av)
    {
        int mem=query_range(id,node*2,l,av,lq,min(av,rq),val);

        if(mem!=lq)
        {
            tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
            return mem;
        }
    }

    tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
    return lq;
}
int on_which[nmax];

int id[nmax];

void create_paths(int node,int par,int root)
{
    on_which[node]=root;
    id[node]=path[root].size();
    path[root].push_back(node);

    //cout<<node<<" -> "<<on_which[node]<<" "<<id[node]<<endl;

    for(auto k:adj[node])
        if(k!=par)
        {
            if(k==heaviest[node])create_paths(k,node,root);
            else create_paths(k,node,k);
        }
}

int fenwick[nmax];

int ask(int pos)
{
    int ret=0;
    while(pos)
    {
        ret+=fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}

void upd(int pos,int val)
{
    while(pos<=n)
    {
        fenwick[pos]+=val;
        pos=pos+(pos&(-pos));
    }
}

long long eval(vector< pair<int/*value*/,int/*how much*/> > given)
{
    long long outp=0;

    for(auto k:given)
    {
        outp=outp+1LL*k.second*ask(k.first-1);

        upd(k.first,k.second);
    }

    for(auto k:given)
    {
        upd(k.first,-k.second);
    }

    return outp;
}

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    compress();

    for(int i=1;i<n;i++)
    {
        scanf("%i%i",&edges[i].first,&edges[i].second);

        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }

    dfs(1,0);

    create_paths(1,0,1);

    for(int i=1;i<=n;i++)
    {
        while(tree[i].size()<4*path[i].size())
        {
            info cur;
            cur.lazy=-1;
            cur.maxi=-1;
            cur.mini=1e9;

            tree[i].push_back(cur);
        }
    }

    for(int i=1;i<=n;i++)
    {
        //cout<<"i= "<<i<<endl;

        update(on_which[i],1,0,path[on_which[i]].size()-1,id[i],id[i],inp[i]);
    }

    for(int i=1;i<n;i++)
    {
        int where=edges[i].first;

        int new_val=inp[edges[i].second];

        vector< pair<int/*value*/,int/*how much*/> > given={};

        while(where)
        {
            //cout<<"where= "<<i<<" "<<where<<endl;

            int cur_value=query(on_which[where],1,0,path[on_which[where]].size()-1,id[where]);

            int le=query_range(on_which[where],1,0,path[on_which[where]].size()-1,0,id[where],cur_value);

            //cout<<"range: "<<le<<" "<<id[where]<<" "<<cur_value<<endl;

            given.push_back({cur_value,id[where]-le+1});

            update(on_which[where],1,0,path[on_which[where]].size()-1,le,id[where],inp[edges[i].second]);

            where=path[on_which[where]][le];
            where=parent[where];

            //system("pause");
        }

        printf("%lld\n",eval(given));
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:266:13: warning: unused variable 'new_val' [-Wunused-variable]
  266 |         int new_val=inp[edges[i].second];
      |             ^~~~~~~
construction.cpp:225:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  225 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
construction.cpp:226:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  226 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
construction.cpp:232:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  232 |         scanf("%i%i",&edges[i].first,&edges[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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