Submission #1088906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088906		DobromirAngelov	Construction of Highway (JOI18_construction)	C++14	100 / 100	713 ms	114884 KiB

construction

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second

using namespace std;

const int MAXN=1e5+5;

struct Fenwick
{
    int n;
    int tree[MAXN];

    void init(int _n)
    {
        n=_n;
        fill(tree+1,tree+n+1,0);
    }

    void update(int idx,int val)
    {
        for(;idx<=n;idx+=idx&(-idx))
        {
            tree[idx]+=val;
        }
    }

    int query(int idx)
    {
        int ret=0;
        for(;idx>0;idx-=idx&(-idx))
        {
            ret+=tree[idx];
        }
        return ret;
    }

    int query(int l,int r)
    {
        return query(r)-query(l-1);
    }
};

int n;
int a[MAXN];
pair<int,int> edges[MAXN];
vector<int> adj[MAXN];
int par[MAXN];
int depth[MAXN];
int heavy[MAXN];
int head[MAXN];
int pos[MAXN];
int ptr=1;
deque<pair<int,int> > chain[MAXN];
Fenwick tree;

int dfs(int v)
{
    int sz=1;
    int maxSz=0;
    for(auto u: adj[v])
    {
        depth[u]=depth[v]+1;
        int curSz=dfs(u);
        if(curSz>maxSz)
        {
            maxSz=curSz;
            heavy[v]=u;
        }
        sz+=curSz;
    }
    return sz;
}

void decompose(int v,int h)
{
    head[v]=h;
    pos[v]=pos[h];
    if(heavy[v]) decompose(heavy[v],h);
    for(auto u: adj[v])
    {
        if(u==heavy[v]) continue;
        pos[u]=ptr++;
        decompose(u,u);
    }
}

void HLD()
{
    depth[1]=1;
    dfs(1);

    pos[1]=ptr++;
    decompose(1,1);
}

vector<pair<int,int> > path;
set<int> s;
map<int,int> code;
long long calcInv(int v)
{
    path.clear();
    while(v>=1)
    {
        int h=head[v];
        int len=depth[v]-depth[h]+1;
        vector<pair<int,int> > tmp;
        for(int i=0;i<chain[pos[v]].size();i++)
        {
            auto cur=chain[pos[v]][i];
            tmp.push_back({cur.fi, min(cur.se,len)});
            len-=cur.se;
            if(len<=0) break;
        }
        reverse(tmp.begin(),tmp.end());
        for(auto x: tmp) path.push_back(x);
        v=par[h];
    }

    s.clear();
    for(auto cur: path) s.insert(cur.fi);
    int ptr=0;
    for(auto x: s) code[x]=++ptr;
    for(auto &cur: path) cur.fi=code[cur.fi];

    tree.init(ptr);
    long long ret=0;
    for(auto cur: path)
    {
        ret+=1LL*tree.query(cur.fi-1)*cur.se;
        tree.update(cur.fi,cur.se);
    }

    return ret;
}

void addEdge(int v,int val)
{
    while(v>=1)
    {
        int h=head[v];
        int len=depth[v]-depth[h]+1;
        while(!chain[pos[v]].empty() && len>0)
        {
            auto cur=chain[pos[v]].front();
            chain[pos[v]].pop_front();
            len-=cur.se;
            if(len<0)
            {
               chain[pos[v]].push_front({cur.fi, -len}); 
            }
        }
        len=depth[v]-depth[h]+1;
        chain[pos[v]].push_front({val,len});
        v=par[h];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        cin>>edges[i].fi>>edges[i].se;
        adj[edges[i].fi].push_back(edges[i].se);
        par[edges[i].se]=edges[i].fi;
    }

    HLD();

    chain[pos[1]].push_front({a[1],1});
    for(int i=1;i<n;i++)
    {
        cout<<calcInv(edges[i].fi)<<endl;
        addEdge(edges[i].se, a[edges[i].se]);
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'long long int calcInv(int)':
construction.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int i=0;i<chain[pos[v]].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~

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