Submission #235055

#	Time	Username	Problem	Language	Result	Execution time	Memory
235055		bvd	Construction of Highway (JOI18_construction)	C++14	7 / 100	2072 ms	3380 KiB

construction

//
// Created by bvd on 5/26/20.
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int inf = (int) 1e9;

struct Result {
    vector<pii> values;
    int inv;
    bool isNil;
};
const Result nil = {vector<pii>(), 0, true};

struct Node {
    static const int maxn = 100000;


    Node *l = 0, *r = 0;
    int lo, hi;
    bool lazy;
    int lazyValue;
    Result val;

    Node(int lo,int hi): lo(lo), hi(hi) { lazy = false; lazyValue = 0; val = nil;}

    void print(Result a) {
        cerr << "values\n";
        for (auto i: a.values) cerr << i.X << ' ' << i.Y << '\n';
        cerr << "inv "; cerr << a.inv << '\n';
        cerr << "isNil "; cerr << a.isNil << '\n';
    }

    Result merge(Result a,Result b) {
        if (a.isNil) return b;
        if (b.isNil) return a;

        //cerr << "a\n"; print(a); cerr << "b\n"; print(b);

        map<int,int> M;
        for(auto i: a.values) M[i.X]+=i.Y;
        for(auto i: b.values) M[i.X]+=i.Y;

        Result res;
        res.values.clear();
        for (auto it=M.begin(); it!=M.end(); it++)
            res.values.pb({(*it).X,(*it).Y});

        int n = sz(a.values), m = sz(b.values);
        vi fa; fa.resize(n);
        fa[n-1] = a.values[n-1].Y;
        for (int i=n-2; i>=0; i--)
            fa[i] = fa[i+1]+a.values[i].Y;

        int aptr = 0;
        res.inv = a.inv+b.inv;
        rep(bptr,0,m) {
            while (aptr < n and a.values[aptr].X<=b.values[bptr].X) aptr++;
            if (aptr==n) break;
            res.inv+=fa[aptr]*b.values[bptr].Y;
        }

        res.isNil = false;
        //cerr << "res\n"; print(res);
        //cerr << '\n';
        return res;
    }

    Result query(int L,int R) {
        if (R <=lo || hi<=L) return {vector<pii>(), 0, true};
        if (L <=lo && hi<=R) return val;
        push();
        return merge(l->query(L,R), r->query(L,R));
    }

    void set(int L,int R,int x) {
        if (R<=lo || hi<=L) return;
        if (L<=lo && hi<=R) {
            val = { {{x,hi-lo}}, 0, false } ;
            lazy = true;
            lazyValue = x;
            return;
        }
        push(); l->set(L,R,x); r->set(L,R,x);
        val = merge(l->val, r->val);
    }

    void push() {
        if (!l) {
            int mid = lo + (hi-lo)/2;
            l = new Node(lo, mid); r = new Node(mid, hi);
        }
        if (lazy) {
            l->set(lo,hi,lazyValue), r->set(lo,hi,lazyValue);
            val.values = {{lazyValue, hi-lo}};
            val.inv = 0;
            val.isNil = false;
            lazy = false;
        }
    }
};


template <bool VALS_EDGES> struct HLD {
    int N, tim = 0;
    vector<vi> adj;
    vi par, siz, depth, rt, pos;
    Node *tree;
    HLD(vector<vi> adj_)
            : N(sz(adj_)), adj(adj_), par(N, -1), siz(N, 1), depth(N),
              rt(N),pos(N),tree(new Node(0, N)){ dfsSz(),dfsHld();}
    void dfsSz(int v = 0) {
        if (par[v] != -1) adj[v].erase(find(all(adj[v]), par[v]));
        for (int& u : adj[v]) {
            par[u] = v, depth[u] = depth[v] + 1;
            dfsSz(u);
            siz[v] += siz[u];
            if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
        }
    }
    void dfsHld(int v = 0) {
        pos[v] = tim++;
        for (int u : adj[v]) {
            rt[u] = (u == adj[v][0] ? rt[v] : u);
            dfsHld(u);
        }
    }
    template <class B> void process(int u, int v, B op) {
        int prev = -1;
        for (; rt[u] != rt[v]; v = par[rt[v]]) {
            if (depth[rt[u]] > depth[rt[v]]) { assert(false); swap(u, v); }
            assert(pos[rt[v]]!=prev);
            op(pos[rt[v]], pos[v] + 1);
            prev = pos[v] + 1;
        }
        if (depth[u] > depth[v]) {assert(false); swap(u, v); }
        assert(pos[u] + VALS_EDGES!=prev);
        op(pos[u] + VALS_EDGES, pos[v] + 1);
    }

    /*void modifyPath(int u, int v, int val) {
        process(u, v, [&](int l, int r) { tree->add(l, r, val); });
    }*/

    void updatePath(int u,int v,int value) {
        process(u, v, [&](int l, int r) {
            tree->set(l, r, value);
        });
    }

    Result queryPath(int u,int v) {
        Result res = {vector<pii>(), 0, true};
        process(u,v,[&](int l,int r) {
            res = tree->merge(tree->query(l,r), res);
        });
        return res;
    }

    /*int queryPath(int u, int v) { // Modify depending on query
        int res = -1e9;
        process(u, v, [&](int l, int r) {
            res = max(res, tree->query(l, r));
        });
        return res;
    }*/

    /*int querySubtree(int v) { // modifySubtree is similar
        return tree->query(pos[v] + VALS_EDGES, pos[v] + siz[v]);
    }*/
};

const int maxn = 100000;
int n;
int c[maxn+1];
int a[maxn+1], b[maxn+1];
vector<vi> G;

main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen("debug.txt","w",stderr);
    cin >> n; rep(i,0,n) cin >> c[i];
    G.resize(n);
    rep(i,0,n-1) {
        int u,v; cin >> u >> v; u--; v--; G[u].pb(v); G[v].pb(u);
        a[i] = u, b[i] = v;
    }
    HLD<false> hld = HLD<false>(G);
    rep(i,0,n) hld.updatePath(i,i,c[i]);
    rep(i,0,n-1) {
        Result res = hld.queryPath(0, a[i]);
        cout << res.inv << '\n';
        hld.updatePath(0, b[i], c[b[i]]);
        //res = hld.queryPath(0,a[i]);
        //cerr << "assert " << a[i] << ' ' << b[i] << ' ' << c[b[i]] << ' ' << sz(res.values) << ' ' << res.values[0].X << ' ' << res.values[0].Y << '\n';
    }
    return 0;
}

Compilation message (stderr)

construction.cpp:188:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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