oj.uz

Submission #235070

# Submission time Handle Problem Language Result Execution time Memory
235070 2020-05-26T22:15:29 Z bvd Construction of Highway (JOI18_construction) C++14
7 / 100
 2000 ms 2760 KB 
//
// Created by bvd on 5/26/20.
//
#include <bits/stdc++.h>
using namespace std;
#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;
    ll inv;
    bool isNil;
};
const Result nil = {vector<pii>(), 0, true};
map<int,int> M;

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);

    M.clear();
    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+=(ll) fa[aptr]*(ll) b.values[bptr].Y;
    }

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

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;}
    Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
        lazy = false;
        lazyValue = 0;
        //cerr << lo << ' ' << hi << endl;
        if (lo + 1 < hi) {
            int mid = lo + (hi - lo)/2;
            l = new Node(v, lo, mid); r = new Node(v, mid, hi);
            val = merge(l->val, r->val);
        }
        else val = { {{v[lo], 1}}, 0, false};
    }

    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 query(int L,int R) {
        if (R <=lo || hi<=L) return nil;
        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_, vi& c)
            : N(sz(adj_)), adj(adj_), par(N, -1), siz(N, 1), depth(N),
              rt(N),pos(N) {
        dfsSz();
        dfsHld();
        vi nc; nc.resize(N);
        rep(i,0,N) nc[pos[i]] = c[i];
        tree = new Node(nc,0,N);
    }
    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 = 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;
vi c;
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) { int x; cin >> x; c.pb(x); }
    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,c);
    rep(i,0,n-1) {
        Result res = hld.queryPath(0, a[i]);
        cout << res.inv << '\n';
        hld.updatePath(0, a[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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 48 ms 512 KB Output is correct
5 Correct 139 ms 640 KB Output is correct
6 Correct 136 ms 760 KB Output is correct
7 Correct 132 ms 640 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 41 ms 640 KB Output is correct
10 Correct 42 ms 640 KB Output is correct
11 Correct 49 ms 640 KB Output is correct
12 Correct 48 ms 640 KB Output is correct
13 Correct 47 ms 640 KB Output is correct
14 Correct 39 ms 640 KB Output is correct
15 Correct 177 ms 640 KB Output is correct
16 Correct 204 ms 760 KB Output is correct
17 Correct 199 ms 640 KB Output is correct
18 Correct 199 ms 640 KB Output is correct
19 Correct 41 ms 640 KB Output is correct
20 Correct 39 ms 640 KB Output is correct
21 Correct 39 ms 692 KB Output is correct
22 Correct 12 ms 512 KB Output is correct
23 Correct 18 ms 512 KB Output is correct
24 Correct 42 ms 632 KB Output is correct
25 Correct 97 ms 640 KB Output is correct
26 Correct 12 ms 640 KB Output is correct
27 Correct 44 ms 640 KB Output is correct
28 Correct 12 ms 640 KB Output is correct
29 Correct 10 ms 640 KB Output is correct
30 Correct 179 ms 640 KB Output is correct
31 Correct 35 ms 632 KB Output is correct
32 Correct 11 ms 640 KB Output is correct
33 Correct 57 ms 640 KB Output is correct
34 Correct 73 ms 672 KB Output is correct
35 Correct 82 ms 640 KB Output is correct
36 Correct 13 ms 640 KB Output is correct
37 Correct 16 ms 512 KB Output is correct
38 Correct 18 ms 512 KB Output is correct
39 Correct 58 ms 760 KB Output is correct
40 Correct 74 ms 640 KB Output is correct
41 Correct 81 ms 640 KB Output is correct
42 Correct 14 ms 640 KB Output is correct
43 Correct 17 ms 512 KB Output is correct
44 Correct 18 ms 640 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 48 ms 512 KB Output is correct
5 Correct 139 ms 640 KB Output is correct
6 Correct 136 ms 760 KB Output is correct
7 Correct 132 ms 640 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 41 ms 640 KB Output is correct
10 Correct 42 ms 640 KB Output is correct
11 Correct 49 ms 640 KB Output is correct
12 Correct 48 ms 640 KB Output is correct
13 Correct 47 ms 640 KB Output is correct
14 Correct 39 ms 640 KB Output is correct
15 Correct 177 ms 640 KB Output is correct
16 Correct 204 ms 760 KB Output is correct
17 Correct 199 ms 640 KB Output is correct
18 Correct 199 ms 640 KB Output is correct
19 Correct 41 ms 640 KB Output is correct
20 Correct 39 ms 640 KB Output is correct
21 Correct 39 ms 692 KB Output is correct
22 Correct 12 ms 512 KB Output is correct
23 Correct 18 ms 512 KB Output is correct
24 Correct 42 ms 632 KB Output is correct
25 Correct 97 ms 640 KB Output is correct
26 Correct 12 ms 640 KB Output is correct
27 Correct 44 ms 640 KB Output is correct
28 Correct 12 ms 640 KB Output is correct
29 Correct 10 ms 640 KB Output is correct
30 Correct 179 ms 640 KB Output is correct
31 Correct 35 ms 632 KB Output is correct
32 Correct 11 ms 640 KB Output is correct
33 Correct 57 ms 640 KB Output is correct
34 Correct 73 ms 672 KB Output is correct
35 Correct 82 ms 640 KB Output is correct
36 Correct 13 ms 640 KB Output is correct
37 Correct 16 ms 512 KB Output is correct
38 Correct 18 ms 512 KB Output is correct
39 Correct 58 ms 760 KB Output is correct
40 Correct 74 ms 640 KB Output is correct
41 Correct 81 ms 640 KB Output is correct
42 Correct 14 ms 640 KB Output is correct
43 Correct 17 ms 512 KB Output is correct
44 Correct 18 ms 640 KB Output is correct
45 Correct 605 ms 1016 KB Output is correct
46 Execution timed out 2082 ms 2760 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 48 ms 512 KB Output is correct
5 Correct 139 ms 640 KB Output is correct
6 Correct 136 ms 760 KB Output is correct
7 Correct 132 ms 640 KB Output is correct
8 Correct 41 ms 760 KB Output is correct
9 Correct 41 ms 640 KB Output is correct
10 Correct 42 ms 640 KB Output is correct
11 Correct 49 ms 640 KB Output is correct
12 Correct 48 ms 640 KB Output is correct
13 Correct 47 ms 640 KB Output is correct
14 Correct 39 ms 640 KB Output is correct
15 Correct 177 ms 640 KB Output is correct
16 Correct 204 ms 760 KB Output is correct
17 Correct 199 ms 640 KB Output is correct
18 Correct 199 ms 640 KB Output is correct
19 Correct 41 ms 640 KB Output is correct
20 Correct 39 ms 640 KB Output is correct
21 Correct 39 ms 692 KB Output is correct
22 Correct 12 ms 512 KB Output is correct
23 Correct 18 ms 512 KB Output is correct
24 Correct 42 ms 632 KB Output is correct
25 Correct 97 ms 640 KB Output is correct
26 Correct 12 ms 640 KB Output is correct
27 Correct 44 ms 640 KB Output is correct
28 Correct 12 ms 640 KB Output is correct
29 Correct 10 ms 640 KB Output is correct
30 Correct 179 ms 640 KB Output is correct
31 Correct 35 ms 632 KB Output is correct
32 Correct 11 ms 640 KB Output is correct
33 Correct 57 ms 640 KB Output is correct
34 Correct 73 ms 672 KB Output is correct
35 Correct 82 ms 640 KB Output is correct
36 Correct 13 ms 640 KB Output is correct
37 Correct 16 ms 512 KB Output is correct
38 Correct 18 ms 512 KB Output is correct
39 Correct 58 ms 760 KB Output is correct
40 Correct 74 ms 640 KB Output is correct
41 Correct 81 ms 640 KB Output is correct
42 Correct 14 ms 640 KB Output is correct
43 Correct 17 ms 512 KB Output is correct
44 Correct 18 ms 640 KB Output is correct
45 Correct 605 ms 1016 KB Output is correct
46 Execution timed out 2082 ms 2760 KB Time limit exceeded
47 Halted 0 ms 0 KB -