Submission #489891

#	Time	Username	Problem	Language	Result	Execution time	Memory
489891		KienTran	Construction of Highway (JOI18_construction)	C++14	100 / 100	1507 ms	231768 KiB

construction

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 3e5 + 5;

int n, cnt, a[O], b[O], c[O], h[O], d[O], E[O], par[O], head[O], child[O], tree[O * 4];
vector <int> val, g[O];

deque <pair <int, int>> q[O];

void Update(int id, int l, int r, int u, int x){
    if (l > u || r < u) return;
    if (l == r){
        tree[id] += x;
        return;
    }
    int mid = (l + r) / 2;
    Update(id << 1, l, mid, u, x);
    Update(id << 1 | 1, mid + 1, r, u, x);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

int Get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l + r) / 2;
    return Get(id << 1, l, mid, u, v) + Get(id << 1 | 1, mid + 1, r, u, v);
}

void dfs(int u){
    child[u] = 1;
    for (int i : g[u]){
        int v = u ^ E[i];
        if (v != par[u]){
            par[v] = u;
            h[v] = h[u] + 1;
            dfs(v);
            child[u] += child[v];
        }
    }
}

void hld(int u){
    if (head[cnt] == 0) head[cnt] = u; d[u] = cnt;

    int Max = -1, BigChild = -1;

    for (int i : g[u]){
        int v = u ^ E[i];
        if (v != par[u] && child[v] > Max){
            Max = child[v];
            BigChild = v;
        }
    }

    if (BigChild != -1) hld(BigChild);

    for (int i : g[u]){
        int v = u ^ E[i];
        if (v != par[u] && v != BigChild){
            cnt += 1;
            hld(v);
        }
    }
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        cin >> c[i];
        val.push_back(c[i]);
    }

    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    int lim = val.size();

    for (int i = 1; i < n; ++ i){
        cin >> a[i] >> b[i];
        g[a[i]].push_back(i);
        E[i] = a[i] ^ b[i];
    }

    dfs(1); hld(1);

    q[d[1]].push_back({1, c[1]});
    for (int i = 1; i < n; ++ i){
        int u = a[i];

        vector <pair <int, int>> need;
        while (u){
            int parU = head[d[u]];
            int k = h[u] - h[parU] + 1;

            vector <pair <int, int>> sth;
            while (k){
                int cost = min(k, q[d[u]][0].first);
                k -= cost;

                sth.push_back({cost, q[d[u]][0].second});

                q[d[u]][0].first -= cost;
                if (q[d[u]][0].first == 0) q[d[u]].pop_front();
            }


            while (sth.size()){
                need.push_back(sth.back());
                sth.pop_back();
            }

            q[d[u]].push_front({h[u] - h[parU] + 1, c[b[i]]});
            u = par[parU];
        }

        u = b[i];
        if (q[d[u]].size() && q[d[u]].back().second == c[u]) q[d[u]].back().first += 1;
        else q[d[u]].push_back({1, c[u]});

        int res = 0;
        for (auto j : need){
            int id = upper_bound(val.begin(), val.end(), j.second) - val.begin();
            res += j.first * Get(1, 1, lim, 1, id - 1);
            Update(1, 1, lim, id, j.first);
        }

        for (auto j : need){
            int id = upper_bound(val.begin(), val.end(), j.second) - val.begin();
            Update(1, 1, lim, id, -j.first);
        }

        cout << res << "\n";
    }
}

Compilation message (stderr)

construction.cpp: In function 'void hld(long long int)':
construction.cpp:46:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   46 |     if (head[cnt] == 0) head[cnt] = u; d[u] = cnt;
      |     ^~
construction.cpp:46:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   46 |     if (head[cnt] == 0) head[cnt] = u; d[u] = cnt;
      |                                        ^
construction.cpp: At global scope:
construction.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

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