Submission #882551

#	Time	Username	Problem	Language	Result	Execution time	Memory
882551		viwlesxq	Construction of Highway (JOI18_construction)	C++17	16 / 100	159 ms	1748 KiB

construction

//     ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//     ➡  IOI, IZhO ⬅
//     ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
//⠀⠀⢠⣤⡄⢠⣤⣤⣤⣤⣤⣤⡄⢠⣤⡄⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⢸⣿⡇⢸⣿⣿⣿⣿⣿⣿⡇⢸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠙⠃⠘⠛⠛⠛⠛⠛⠛⠃⠘⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀  ⠘⠛⠛⠛⠛⠛⠛⠛⠛⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⣠⣶⣶⠂⣰⣶⣶⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⢀⣾⣿⣿⡏⢠⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⡈⠻⣿⣿⣶⣾⣿⣿⣿⣿⠿⠋⡀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⣿⣶⣄⠙⣿⣿⣿⣿⣟⢁⣴⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⢹⣿⡏⢠⣿⠟⠛⢿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠙⠀⠀⣠⣶⣷⣤⡈⠛⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠋⠉⠀⠀


#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
#define pb push_back
#define eb emplace_back

template<typename S>
bool chmin(S &a, const S b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename S>
bool chmax(S &a, const S b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const double eps = 1e-6;
const double EPS = 1e-9;

vector<int> path, g[4000];

struct Fenwick_Tree {
    int n;
    vector<int> t;
    Fenwick_Tree(int n) {
        this->n = n;
        t.assign(n, 0);
    }
    void upd(int i) {
        for (; i < n; i = i | (i + 1)) {
            t[i]++;
        }
    }
    int get(int i) {
        int res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) {
            res += t[i];
        }
        return res;
    }
};

void compress(vector<int> &c) {
    vector<int> v;
    unordered_map<int, int> mp;
    for (int i = 0; i < size(c); ++i) {
        if (!mp.count(c[i])) {
            v.pb(c[i]);
            mp[c[i]];
        }
    }
    sort(all(v));
    for (int i = 0; i < size(v); ++i) {
        mp[v[i]] = i;
    }
    for (int i = 0; i < size(c); ++i) {
        c[i] = mp[c[i]];
    }
}

bool dfs(int v, int p, int f) {
    if (v == f) {
        path.pb(v);
        return true;
    }
    for (int to : g[v]) {
        if (to == p) {
            continue;
        }
        if (dfs(to, v, f)) {
            path.pb(v);
            return true;
        }
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    compress(c);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a--, --b;
        path.clear();
        dfs(0, -1, a);
        reverse(all(path));
        Fenwick_Tree t(4000);
        t.upd(c[path[0]]);
        c[path[0]] = c[b];
        g[a].pb(b);
        g[b].pb(a);
        int res = 0;
        for (int j = 1; j < size(path); ++j) {
            t.upd(c[path[j]]);
            res += j + 1 - t.get(c[path[j]]);
            c[path[j]] = c[b];
        }
        cout << res << '\n';
    }
}

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