Submission #1308032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308032		mpawicka_77	Construction of Highway (JOI18_construction)	C++20	100 / 100	1459 ms	24880 KiB

construction

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3, MAXN=(1<<20);
int depth[N], pre[N], tree_size[N], anc[N][19];
int maxx[2*MAXN];
vector<int>V[N];
int a[N], b[N], c[N], num[N];
int licz=1;

void dfs(int v, int p, int d)
{
    depth[v]=d;
    anc[v][0]=p;
    pre[v]=licz++;
    tree_size[v]=1;
    for(auto x:V[v])
    {
        if(x==p)continue;
        dfs(x, v, d+1);
        tree_size[v]+=tree_size[x];
    }
}
void update(int x, int val)
{
    x+=MAXN;
    maxx[x]=val;
    x/=2;
    while(x>0)
    {
        maxx[x]=max(maxx[2*x], maxx[2*x+1]);
        x/=2;
    }
}
int query(int a, int b)
{
    a+=MAXN-1, b+=MAXN+1;
    int res=0;
    while(a/2 != b/2)
    {
        if(a%2==0)res=max(res, maxx[a+1]);
        if(b%2==1)res=max(res, maxx[b-1]);
        a/=2, b/=2;
    }
    return res;
}
pair<vector<pair<int,int>>,long long> calc_ans(vector<pair<int,int>>vec)
{
    if(vec.size()<=1) return {vec, 0};

    vector<pair<int,int>>vec1, vec2;
    for(int i=0; i<vec.size()/2; i++)vec1.push_back(vec[i]);
    for(int i=vec.size()/2; i<vec.size(); i++)vec2.push_back(vec[i]);


    auto X1=calc_ans(vec1), X2=calc_ans(vec2);
    vec1=X1.first, vec2=X2.first;
    long long res=X1.second+X2.second;

    long long ind=0, ile=0;
    for(int i=0; i<vec1.size(); i++)
    {
        while(ind<vec2.size()&&vec2[ind].first<vec1[i].first)
        {
            ile+=vec2[ind].second;
            ind++;
        }
        res+=ile*vec1[i].second;
    }
    vec.clear();
    int i=0, j=0;
    while(i<vec1.size()||j<vec2.size())
    {
        if(i>=vec1.size())vec.push_back(vec2[j++]);
        else if(j>=vec2.size())vec.push_back(vec1[i++]);
        else if (vec1[i]<vec2[j])vec.push_back(vec1[i++]);
        else vec.push_back(vec2[j++]);
    }
    return {vec, res};
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>c[i];
    for(int i=1; i<n; i++)
    {
        cin>>a[i]>>b[i];
        V[a[i]].push_back(b[i]);
        V[b[i]].push_back(a[i]);
    }
    dfs(1,1,1);
    for(int pot=1; pot<=17; pot++)
    {
        for(int i=1; i<=n; i++)
        {
            anc[i][pot]=anc[anc[i][pot-1]][pot-1];
        }
    }
    num[0]=c[1];
    for(int i=1; i<n; i++)
    {
        num[i]=c[b[i]];
        vector<pair<int,int>>vec;
        int wcz=a[i];
        while(true)
        {
            int x=wcz, t=query(pre[x], pre[x]+tree_size[x]-1);
            for(int pot=17; pot>=0; pot--)
            {
                int u=anc[x][pot];
                if(t==query(pre[u], pre[u]+tree_size[u]-1))
                {
                    x=u;;
                }
            }
            vec.push_back({num[t], depth[wcz]-depth[x]+1});
            if(x==1)break;
            wcz=anc[x][0];
        }
        reverse(vec.begin(), vec.end());
       // for(auto x:vec)cout<<x.first<<" "<<x.second<<"\n";
        cout<<calc_ans(vec).second<<"\n";
        update(pre[b[i]], i);
    }
    return 0;
}

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