Submission #1031296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031296		underwaterkillerwhale	Construction of Highway (JOI18_construction)	C++17	100 / 100	162 ms	20352 KiB

construction

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const ll INF = 1e9 + 160907;
const int BASE = 137;

int n, m;
int a[N];
vector<int> ke[N];
vector<pair<int,int>> vec[N];
pair<int,int> qr[N];

struct fenwick_Tree {
    int m;
    int fen[N];
    void init (int n) {
        m = n;
        rep (i, 1, m) fen[i] = 0;
    }
    void update (int pos, int val) {
        for (; pos <= m; pos += pos & -pos) fen[pos] += val;
    }
    int get (int pos) {
        int res = 0;
        for (;pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
}fen;

int cid[N], Head[N], par[N], high[N], nChild[N], numC = 1, in[N];

void pdfs (int u, int p) {
    par[u] = p;
    nChild[u] = 1;
    high[u] = high[p] + 1;
    iter (&v, ke[u]) if (v != p){
        pdfs(v, u);
        nChild[u] += nChild[v];
    }
}

void hld (int u, int p) {
    static int time_dfs = 0;
    if (numC != cid[p]) Head[u] = u;
    else Head[u] = Head[p];
    in[u] = ++time_dfs;
    cid[u] = numC;
    int mxV = -1;
//    cout << u <<" "<<cid[u] <<" "<<Head[u]<<"\n";
    iter (&v, ke[u]) {
        if (v != p && (v == -1 || nChild[v] > nChild[mxV])) {
            mxV = v;
        }
    }
    if (mxV != -1) hld (mxV, u);
    iter (&v, ke[u]) {
        if (v == p || v == mxV) continue;
        ++numC;
        hld(v, u);
    }
}

ll update (int u, int col) {
//    cout << u <<" "<<col<<": \n";
    static vector<pair<int,int>> chains; chains.clear();
    for (; u != 0; u = par[Head[u]]) chains.push_back({cid[u], high[u] - high[Head[u]] + 1});
    reverse(ALL(chains));
    static vector<pair<int,int>> del; del.clear();
    static vector<int> vals; vals.clear();
    iter (&ch, chains) {
        vector<pair<int,int>> &cur = vec[ch.fs];
        int X = ch.se;
        int pre = 0;
        while (!cur.empty()) {
            pair<int,int> &u = cur.back();
            if (pre + u.se > X) {
                u.se = u.se - (X - pre);
                vals.push_back(u.fs);
                del.push_back({u.fs, X - pre});
                break;
            }
            else {
                del.push_back(u);
                vals.push_back(u.fs);
                pre += u.se;
                cur.pop_back();
            }
        }
        cur.push_back({col, X});
    }
//    iter (&id, del) cout << id.fs<<","<<id.se << " ";
//    cout<<"\n";
//    iter (&id, vec[1]) cout << id.fs<<","<<id.se<<" "; cout <<"\n";
    int ntot;
    sort (ALL(vals));
    vals.resize(ntot = unique(ALL(vals)) - vals.begin());
    fen.init(ntot);
    ll res = 0;
    iter (&cur, del) {
        int pos = lower_bound(ALL(vals), cur.fs) - vals.begin() + 1;
        res += 1LL * (fen.get(ntot) - fen.get(pos)) * cur.se;
        fen.update(pos, cur.se);
    }
    return res;
}

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        qr[i] = {u, v};
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    pdfs(1, 0);
    hld(1, 0);
    vec[1].push_back({a[1], 1});
    rep (i, 1, n - 1) {
        int u, v;
        tie(u, v) = qr[i];
        cout << update (v, a[v]) <<"\n";
    }
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
nghĩ xem mình có thể làm gì, có khả năng làm những gì với giới hạn bài toán, đặc điểm bài toans
nếu struggle, xem lại các dữ liệu bài toán xem mình đang xét trường hợp này có phù hợp với các dữ liệu bài toán cung cấp không ?
1
7 3
0010010
110

1
10 4
00xx000xx0x
  11   11 1
1101
L        R
    L         R
*/

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