제출 #1249801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249801		chikien2009	Construction of Highway (JOI18_construction)	C++20	100 / 100	146 ms	22424 KiB

construction

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct FENWICK_TREE
{
    int tree[100001], tree_size;
    inline void Init(int new_size)
    {
        tree_size = new_size;
        fill_n(tree, tree_size + 1, 0);
    }
    inline void Add(int x, int v)
    {
        while (x <= tree_size)
        {
            tree[x] += v;
            x += (x & (~(x - 1)));
        }
    }
    inline int Get(int x)
    {
        int res = 0;
        while (0 < x)
        {
            res += tree[x];
            x -= (x & (~(x - 1)));
        }
        return res;
    }
} ft;

int n;
int a[100000], b[100000], c[100000], d[100000];
int depth[100000], sz[100000], head[100000], par[100000];
vector<int> g[100000];
vector<pair<int, int>> v[100000], cur, temp;

inline bool Comp(const int &ina, const int &inb)
{
    return sz[ina] > sz[inb];
}

inline void DFS(int node)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        depth[i] = depth[node] + 1;
        par[i] = node;
        DFS(i);
        sz[node] += sz[i];
    }
    sort(g[node].begin(), g[node].end(), Comp);
}

inline void HLD(int node, int chain)
{
    head[node] = (chain == -1 ? node : chain);
    for (int i = 0; i < g[node].size(); ++i)
    {
        HLD(g[node][i], (i == 0 ? head[node] : -1));
    }
}

inline void GoUp(int node, int new_val)
{
    temp.clear();
    while (!v[head[node]].empty() && v[head[node]].back().second <= depth[node])
    {
        temp.push_back(v[head[node]].back());
        v[head[node]].pop_back();
    }
    if (!v[head[node]].empty())
    {
        temp.push_back({v[head[node]].back().first, depth[node]});
    }
    v[head[node]].push_back({new_val, depth[node]});
    while (!temp.empty())
    {
        cur.push_back(temp.back());
        temp.pop_back();
    }
    if (par[head[node]] != -1)
    {
        GoUp(par[head[node]], new_val);
    }
}

inline long long Val(vector<pair<int, int>> &inp)
{
    int m;
    long long res = 0, h;
    for (int i = 0; i < inp.size(); ++i)
    {
        d[i] = inp[i].first;
    }
    sort(d, d + inp.size());
    m = unique(d, d + inp.size()) - d;
    ft.Init(m);
    for (int i = 0; i < inp.size(); ++i)
    {
        inp[i].first = lower_bound(d, d + m, inp[i].first) - d + 1;
        h = (i == inp.size() - 1 ? inp[i].second : inp[i].second - inp[i + 1].second);
        res += h * (ft.Get(inp[i].first - 1));
        ft.Add(inp[i].first, h);
    }
    return res;
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i];
        d[i] = c[i];
    }
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        g[a[i]].push_back(b[i]);
    }
    depth[0] = 1;
    par[0] = -1;
    v[0].push_back({c[0], 1});
    DFS(0);
    HLD(0, -1);
    sort(d, d + n);
    for (int i = 0; i < n - 1; ++i)
    {
        cur.clear();
        GoUp(b[i], c[b[i]]);
        cout << Val(cur) << "\n";
    }
    return 0;
}

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