Submission #1171331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171331		HoriaHaivas	Construction of Highway (JOI18_construction)	C++20	100 / 100	349 ms	90696 KiB

construction

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

int c[100005];
int x[100005];
int y[100005];
int sz[100005];
int h[100005];
int heavychild[100005];
int pathend[100005];
int p[100005];
vector<int> nodes[100005];
deque<pair<int,int>> lant[100005];

void dfs(int node, int parent)
{
    int mx;
    sz[node]=1;
    p[node]=parent;
    mx=0;
    for (auto x : nodes[node])
    {
        if (x!=parent)
        {
            h[x]=h[node]+1;
            dfs(x,node);
            sz[node]+=sz[x];
            if (sz[x]>sz[mx])
                mx=x;
        }
    }
    heavychild[node]=mx;
}

void heavyfirst(int node, int parent, int capat)
{
    //lant[capat].push_back(node);
    pathend[node]=capat;
    if (heavychild[node]==0)
        return;
    heavyfirst(heavychild[node],node,capat);
    for (auto x : nodes[node])
    {
        if (x!=heavychild[node] && x!=parent)
        {
            heavyfirst(x,node,x);
        }
    }
}

class AIB
{
public:
    int aib[100005];
    int lim;
    void clr()
    {
        int i;
        for (i=1; i<=lim; i++)
        {
            aib[i]=0;
        }
    }
    void update(int idx, int delta)
    {
        while(idx<=lim)
        {
            aib[idx]+=delta;
            idx+=idx&(-idx);
        }
    }
    int query(int idx)
    {
        int ans;
        ans=0;
        while (idx>0)
        {
            ans+=aib[idx];
            idx-=idx&(-idx);
        }
        return ans;
    }
} aib;

vector<pair<int,int>> pathvals;
vector<pair<int,int>> aux;
vector<int> idk;
map<int,int> normval;

int build_cost(int v)
{
    int currnode,diff;
    pathvals.clear();
    currnode=v;
    while (currnode!=0)
    {
        diff=h[currnode]-h[pathend[currnode]]+1;
        aux.clear();
        for (auto x : lant[pathend[currnode]])
        {
            if (diff>x.second)
            {
                aux.push_back(x);
                diff-=x.second;
            }
            else
            {
                aux.push_back({x.first,diff});
                reverse(aux.begin(),aux.end());
                for (auto x : aux)
                    pathvals.push_back(x);
                break;
            }
        }
        currnode=p[pathend[currnode]];
    }
    idk.clear();
    for (auto x : pathvals)
    {
        idk.push_back(x.first);
    }
    sort(idk.begin(),idk.end());
    int currval,i;
    currval=0;
    normval.clear();
    for (i=0; i<idk.size(); i++)
    {
        if (i==0 || idk[i]!=idk[i-1])
            currval++;
        normval[idk[i]]=currval;
    }
    aib.lim=currval;
    aib.clr();
    int ans;
    ans=0;
    for (auto x : pathvals)
    {
        ans+=x.second*(aib.query(normval[x.first]));
        aib.update(normval[x.first]+1,x.second);
    }
    return ans;
}

void add_edge(int u, int v)
{
    int currnode,diff,total;
    currnode=u;
    while (currnode!=0)
    {
        diff=h[currnode]-h[pathend[currnode]]+1;
        total=diff;
        while (diff>0)
        {
            pair<int,int> fr;
            fr=lant[pathend[currnode]].front();
            if (diff>fr.second)
            {
                diff-=fr.second;
                lant[pathend[currnode]].pop_front();
            }
            else
            {
                if (fr.second!=diff)
                    lant[pathend[currnode]].front().second-=diff;
                else
                    lant[pathend[currnode]].pop_front();
                lant[pathend[currnode]].push_front({c[v],total});
                diff=0;
            }
        }
        currnode=p[pathend[currnode]];
    }
    if (!lant[pathend[v]].empty())
        lant[pathend[v]].back().second++;
    else
        lant[pathend[v]].push_back({c[v],1});
}

signed main()
{
    //ifstream fin("secvp.in");
    //ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,u,v;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> c[i];
    }
    for (i=1; i<=n-1; i++)
    {
        cin >> u >> v;
        x[i]=u;
        y[i]=v;
        nodes[u].push_back(v);
        nodes[v].push_back(u);
    }
    h[1]=1;
    dfs(1,0);
    heavyfirst(1,0,1);
    lant[1].push_back({c[1],1});
    for (i=1; i<=n-1; i++)
    {
        cout << build_cost(x[i]) << "\n";
        add_edge(x[i],y[i]);
    }
    return 0;
}

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