Submission #478319

#	Time	Username	Problem	Language	Result	Execution time	Memory
478319		Mike4235	Construction of Highway (JOI18_construction)	C++17	0 / 100	7 ms	9932 KiB

construction

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
// #define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int n, now;
int a[100005], b[100005], c[100005], fentree[100005];
int sz[100005], par[100005], nxt[100005], tin[100005];
vector<pii> ele[100005];
vector<int> g[100005];

void dfs_sz(int u) {
    sz[u] = 1;
    for (auto &v : g[u]) {
        par[v] = u;
        dfs_sz(v);
        if (sz[v] > sz[g[u][0]]) swap(v, g[u][0]);
        sz[u] += sz[v];
    }
}

void dfs_hld(int u) {
    tin[u] = ++now;
    for (auto v : g[u]) {
        nxt[v] = (v == g[u][0] ? nxt[u] : v);
        if (sz(ele[nxt[v]]) && ele[nxt[v]].back().first == c[v]) ele[nxt[v]].back().second++;
        else ele[nxt[v]].push_back({c[v], 1});
        dfs_hld(v);
    }
}

void update(int i, int val) {
    for (; i <= n; i += i & -i) fentree[i] += val;
}

int get(int i) {
    int res = 0;
    for (; i; i -= i & -i) res += fentree[i];
    return res;
}

int solve(int u) {
    vector<pii> q;

    while (u != 0) {
        vector<pii> tmp;
        int cur = 0, sz = tin[u] - tin[nxt[u]] + 1;
        for (auto p : ele[nxt[u]]) {
            if (cur + p.second <= sz) {
                tmp.push_back(p);
                cur += p.second;
            }
            else {
                if (cur < sz) tmp.push_back({p.first, sz - cur});
                break;
            }
        }

        reverse(tmp.begin(), tmp.end());
        for (auto p : tmp) q.push_back(p);

        u = par[nxt[u]];
    }

    int res = 0;
    for (auto p : q) {
        res += p.second * get(p.first - 1);
        update(p.first, p.second);
    }
    for (auto p : q) update(p.first, -p.second);

    return res;
}

void assign(int u, int val) {
    while (u != 0) {
        int cur = 0, sz = tin[u] - tin[nxt[u]] + 1;
        reverse(ele[nxt[u]].begin(), ele[nxt[u]].end());
        while (cur < sz) {
            auto p = ele[nxt[u]].back();
            if (cur + p.second <= sz) {
                cur += p.second;
                ele[nxt[u]].pop_back();
            }
            else {
                ele[nxt[u]].back().second -= sz - cur;
                break;
            }
        }
        if (sz(ele[nxt[u]]) && ele[nxt[u]].back().first == val) ele[nxt[u]].back().second += sz; 
        else ele[nxt[u]].push_back({val, sz});
        reverse(ele[nxt[u]].begin(), ele[nxt[u]].end());
        u = par[nxt[u]];
    }
}

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

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n;
    for1(i,1,n) cin >> c[i];

    for1(i,1,n - 1) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
    }

    ele[1].push_back({c[1], 1});
    dfs_sz(1);
    dfs_hld(1);

    for1(i,1,n - 1) {
        cout << solve(a[i]) << "\n";
        assign(a[i], c[b[i]]);
    }
    
}

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