oj.uz

Submission #478311

# Submission time Handle Problem Language Result Execution time Memory
478311 2021-10-07T02:04:12 Z Mike4235 Construction of Highway (JOI18_construction) C++17
0 / 100
 7 ms 9944 KB 
/*#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) {
    int cur = 0, sz = tin[u] - tin[nxt[u]] + 1;
    vector<pii> q;
    for (auto p : ele[nxt[u]]) {
        if (cur + p.second <= sz) {
            q.push_back(p);
            cur += p.second;
        }
        else {
            if (cur < sz) q.push_back({p.first, sz - cur});
            break;
        }
    }
    reverse(q.begin(), q.end());

    u = par[nxt[u]];
    while (u != 0) {
        for2(i,sz(ele[nxt[u]]) - 1,0) q.push_back(ele[nxt[u]][i]);
        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) {
    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;
        }
    }
    ele[nxt[u]].push_back({val, sz});
    reverse(ele[nxt[u]].begin(), ele[nxt[u]].end());

    u = par[nxt[u]];
    while (u != 0) {
        ele[nxt[u]] = {{val, tin[u] - tin[nxt[u]] + 1}};
        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]);
    }

    nxt[1] = 1;
    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.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -