Submission #486434

#	Time	Username	Problem	Language	Result	Execution time	Memory
486434		blue	Construction of Highway (JOI18_construction)	C++17	100 / 100	259 ms	86380 KiB

construction

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

const int maxN = 100'000;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>; //liveliness, count
using vpii = vector<pii>;

int N;
vi C(1+maxN);

vi A(maxN), B(maxN);

vi parent(1+maxN, 0);
vi childlist[1+maxN];

vi subtree(1+maxN, 1);

vi chain(1+maxN, 0);
int chain_ct = 0;

vi chain_head(1+maxN, 0);

deque<pii> chain_list[1+maxN];

vi depth(1+maxN, 0);

void dfs(int u)
{
    int main_child = -1;
    for(int v: childlist[u])
    {
        depth[v] = 1 + depth[u];
        dfs(v);
        subtree[u] += subtree[v];

        if(main_child == -1 || subtree[v] > subtree[main_child])
            main_child = v;
    }

    if(main_child == -1)
    {
        chain_ct++;
        chain[u] = chain_ct;
    }
    else
        chain[u] = chain[main_child];

    chain_head[ chain[u] ] = u;
}



deque<pii> lst;


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

    cin >> N;
    for(int i = 1; i <= N; i++) cin >> C[i];

    for(int j = 1; j <= N-1; j++)
    {
        cin >> A[j] >> B[j];

        parent[B[j]] = A[j];
        childlist[A[j]].push_back(B[j]);
    }

    dfs(1);

    // for(int i = 1; i <= N; i++) cerr << chain[i] << ' ';
    // cerr << '\n';

    chain_list[ chain[1] ].push_back(make_pair(C[1], 1));

    for(int j = 1; j <= N-1; j++)
    {
        // cerr << "\n\n\n";
        // cerr << "j = " << j << ": \n";
        lst.clear();
        // cerr << A[j] << " -> " << B[j] << '\n';

        vpii query_markers;

        for(int c = A[j]; c != 0; c = parent[ chain_head[ chain[ c ] ] ])
        {

            // cerr << "querying vertex: " << c << ", " << depth[c] - depth[ chain_head[ chain[c] ] ] + 1 << "\n";
            query_markers.push_back(make_pair(chain[c], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
        }

        // reverse(query_markers.begin(), query_markers.end());

        // for(int c = chain_head[ chain[A[j]] ]; c != 0; c = chain_head[ chain[ parent[c] ] ])
        // {
        //     query_list.push_back(chain[c]);
        //     // cerr << "getting from node " << c << "\n";
        //     // for(pii l: chain_list[chain[c]])
        //     //     lst.push_front(l);
        // }

        reverse(query_markers.begin(), query_markers.end());

        for(auto q: query_markers)
        {
            int f = q.second;

            int cf = 0;
            for(pii l: chain_list[q.first])
            {
                int r_cf = min(f-cf, l.second);

                cf += r_cf;

                // lst.push_back(l);
                lst.push_back(make_pair(l.first, r_cf));

                if(cf == f) break;
            }
        }

        // reverse(lst.begin(), lst.end());

        int ls = int(lst.size());

        // for(pii q: lst) cerr << q.first << ' ' << q.second << " | ";
        // cerr << '\n';


        vi I(ls);
        for(int i = 0; i < ls; i++)
        {
            I[i] = i;
        }

        sort(I.begin(), I.end(), [] (int u, int v)
        {
            if(lst[u].first != lst[v].first) return lst[u].first > lst[v].first;
            else return u > v;
        });

        ll ans = 0;

        vll BIT(1 + ls, 0);

        for(int i:I)
        {
            for(int q = i+1; q >= 1; q -= q&-q)
                ans += BIT[q] * lst[i].second;

            for(int q = i+1; q <= ls; q += q&-q)
                BIT[q] += lst[i].second;
        }

        cout << ans << '\n';

        chain_list[chain[B[j]]].push_back(make_pair(C[B[j]], 1));

        deque<pii> update_chains;

        for(int c = B[j]; c != 0; c = parent[ chain_head[ chain[c] ] ])
        {
            // cerr << "updating vertex " << c << '\n';
            update_chains.push_front(make_pair(chain[c], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
        }

        for(pii u: update_chains)
        {
            // cerr << "u = " << u.first << ' ' << u.second << '\n';
            int origin_remain = u.second;
            int remain = u.second;
            int c = u.first;

            while(remain > 0)
            {
                int rx = chain_list[c][0].second;
                int r = min(remain, rx);
                chain_list[c][0].second -= r;
                remain -= r;

                if(chain_list[c][0].second == 0)
                    chain_list[c].pop_front();
            }

            chain_list[c].push_front(make_pair(C[B[j]], origin_remain));

            // cerr << "pushing " << origin_remain << " of " << C[B[j]] << " at the head of chain " << c << '\n';
        }

        // for(int c = B[j]; c != 0; c = parent[ chain_head[ chain[c] ] ])
        // {
        //     cerr << "updating " << chain[c] << " = " << C[B[j]] << ", " << depth[c] - depth[ chain_head[ chain[c] ] ] + 1 << '\n';
        //     chain_list[chain[c]].clear();
        //     chain_list[chain[c]].push_back(make_pair(C[B[j]], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
        // }
    }
}

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