제출 #1283809

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

construction

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e5 + 5;
const int M = 3e6 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18 + 5;
const int P = 31;
const int MOD = 998244353;

struct Fenwick
{
    vector<int> ft;
    int n;
    Fenwick(int len)
    {
        n = len;
        ft.assign(n + 1, 0);
    }
    void update(int pos, int val)
    {
        while (pos <= n)
        {
            ft[pos] += val;
            pos += LSOne(pos);
        }
    }
    int get(int pos)
    {
        int sum = 0;
        while (pos > 0)
        {
            sum += ft[pos];
            pos -= LSOne(pos);
        }
        return sum;
    }
    int get(int l, int r)
    {
        if (l > r)
            return 0;
        return get(r) - get(l - 1);
    }
};

int n, a[N], d[N], par[N], id[N], cid, top[N], bigchild[N], depth[N];
pair<int, int> edges[N];
vector<int> adj[N];
vector<pair<int, int>> val[N], cur, temp;

int dfs1(int c, int p)
{
    par[c] = p;
    int sz = 1, x = -1;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        depth[i] = depth[c] + 1;
        int j = dfs1(i, c);
        sz += j;
        if (j > x)
        {
            bigchild[c] = i;
            x = j;
        }
    }
    return sz;
}

void dfs2(int c, int p)
{
    id[c] = cid++;
    top[c] = p;
    val[p].push_back({a[c], depth[c]});
    if (bigchild[c] == -1)
    {
        reverse(val[p].begin(), val[p].end());
        return;
    }
    dfs2(bigchild[c], p);
    for (int i : adj[c])
    {
        if (i == bigchild[c] || i == par[c])
            continue;
        dfs2(i, i);
    }
}

void lift(int c, int v)
{
    for (; c != 0; c = par[top[c]])
    {
        // for(auto &[a, b] : val[top[c]])
        // {
        //     cout << a << " " << b << "\n";
        // }
        // cout << "v\n";
        while (!val[top[c]].empty() && val[top[c]].back().second <= depth[c])
        {
            temp.push_back(val[top[c]].back());
            val[top[c]].pop_back();
        }
        if (!val[top[c]].empty())
        {
            temp.push_back({val[top[c]].back().first, depth[c]});
        }
        val[top[c]].push_back({v, depth[c]});
        while (!temp.empty())
        {
            cur.push_back(temp.back());
            temp.pop_back();
        }
    }
}

int get()
{
    int m = 0, ans = 0;
    vector<int> v;
    for(auto &[i, j] : cur)
    {
        v.push_back(i);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    Fenwick ft(v.size());
    for(int x = 0; x < cur.size(); x++)
    {
        // cout << cur[x].first << " " << cur[x].second << "\n";
        int len = x == cur.size() -1 ? cur[x].second : cur[x].second - cur[x + 1].second;
        cur[x].first = lower_bound(v.begin(), v.end(), cur[x].first) - v.begin() + 1;
        ans += len * ft.get(cur[x].first - 1);
        ft.update(cur[x].first, len);
    }
    return ans;
}

void solve()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> a[x];
        d[x] = a[x];
        bigchild[x] = -1;
    }
    for (int x = 0; x < n - 1; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        edges[x] = {a, b};
    }
    depth[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    for (int x = 0; x < n - 1; x++)
    {
        cur.clear();
        lift(edges[x].first, a[edges[x].second]);
        cout << get() << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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