oj.uz

Submission #235055

# Submission time Handle Problem Language Result Execution time Memory
235055 2020-05-26T21:08:30 Z bvd Construction of Highway (JOI18_construction) C++14
7 / 100
 2000 ms 3380 KB 
//
// 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

construction.cpp:188: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 6 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 12 ms 512 KB Output is correct
4 Correct 78 ms 640 KB Output is correct
5 Correct 217 ms 760 KB Output is correct
6 Correct 210 ms 768 KB Output is correct
7 Correct 213 ms 768 KB Output is correct
8 Correct 83 ms 768 KB Output is correct
9 Correct 82 ms 864 KB Output is correct
10 Correct 83 ms 768 KB Output is correct
11 Correct 118 ms 768 KB Output is correct
12 Correct 125 ms 888 KB Output is correct
13 Correct 137 ms 760 KB Output is correct
14 Correct 106 ms 760 KB Output is correct
15 Correct 252 ms 768 KB Output is correct
16 Correct 281 ms 888 KB Output is correct
17 Correct 284 ms 768 KB Output is correct
18 Correct 283 ms 760 KB Output is correct
19 Correct 109 ms 888 KB Output is correct
20 Correct 109 ms 760 KB Output is correct
21 Correct 107 ms 768 KB Output is correct
22 Correct 29 ms 640 KB Output is correct
23 Correct 24 ms 640 KB Output is correct
24 Correct 65 ms 640 KB Output is correct
25 Correct 165 ms 888 KB Output is correct
26 Correct 19 ms 640 KB Output is correct
27 Correct 109 ms 888 KB Output is correct
28 Correct 23 ms 640 KB Output is correct
29 Correct 21 ms 640 KB Output is correct
30 Correct 251 ms 760 KB Output is correct
31 Correct 48 ms 640 KB Output is correct
32 Correct 22 ms 640 KB Output is correct
33 Correct 146 ms 888 KB Output is correct
34 Correct 151 ms 768 KB Output is correct
35 Correct 147 ms 760 KB Output is correct
36 Correct 32 ms 640 KB Output is correct
37 Correct 37 ms 640 KB Output is correct
38 Correct 28 ms 640 KB Output is correct
39 Correct 131 ms 888 KB Output is correct
40 Correct 188 ms 760 KB Output is correct
41 Correct 149 ms 760 KB Output is correct
42 Correct 25 ms 640 KB Output is correct
43 Correct 27 ms 640 KB Output is correct
44 Correct 29 ms 640 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 12 ms 512 KB Output is correct
4 Correct 78 ms 640 KB Output is correct
5 Correct 217 ms 760 KB Output is correct
6 Correct 210 ms 768 KB Output is correct
7 Correct 213 ms 768 KB Output is correct
8 Correct 83 ms 768 KB Output is correct
9 Correct 82 ms 864 KB Output is correct
10 Correct 83 ms 768 KB Output is correct
11 Correct 118 ms 768 KB Output is correct
12 Correct 125 ms 888 KB Output is correct
13 Correct 137 ms 760 KB Output is correct
14 Correct 106 ms 760 KB Output is correct
15 Correct 252 ms 768 KB Output is correct
16 Correct 281 ms 888 KB Output is correct
17 Correct 284 ms 768 KB Output is correct
18 Correct 283 ms 760 KB Output is correct
19 Correct 109 ms 888 KB Output is correct
20 Correct 109 ms 760 KB Output is correct
21 Correct 107 ms 768 KB Output is correct
22 Correct 29 ms 640 KB Output is correct
23 Correct 24 ms 640 KB Output is correct
24 Correct 65 ms 640 KB Output is correct
25 Correct 165 ms 888 KB Output is correct
26 Correct 19 ms 640 KB Output is correct
27 Correct 109 ms 888 KB Output is correct
28 Correct 23 ms 640 KB Output is correct
29 Correct 21 ms 640 KB Output is correct
30 Correct 251 ms 760 KB Output is correct
31 Correct 48 ms 640 KB Output is correct
32 Correct 22 ms 640 KB Output is correct
33 Correct 146 ms 888 KB Output is correct
34 Correct 151 ms 768 KB Output is correct
35 Correct 147 ms 760 KB Output is correct
36 Correct 32 ms 640 KB Output is correct
37 Correct 37 ms 640 KB Output is correct
38 Correct 28 ms 640 KB Output is correct
39 Correct 131 ms 888 KB Output is correct
40 Correct 188 ms 760 KB Output is correct
41 Correct 149 ms 760 KB Output is correct
42 Correct 25 ms 640 KB Output is correct
43 Correct 27 ms 640 KB Output is correct
44 Correct 29 ms 640 KB Output is correct
45 Correct 937 ms 1144 KB Output is correct
46 Execution timed out 2072 ms 3380 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 12 ms 512 KB Output is correct
4 Correct 78 ms 640 KB Output is correct
5 Correct 217 ms 760 KB Output is correct
6 Correct 210 ms 768 KB Output is correct
7 Correct 213 ms 768 KB Output is correct
8 Correct 83 ms 768 KB Output is correct
9 Correct 82 ms 864 KB Output is correct
10 Correct 83 ms 768 KB Output is correct
11 Correct 118 ms 768 KB Output is correct
12 Correct 125 ms 888 KB Output is correct
13 Correct 137 ms 760 KB Output is correct
14 Correct 106 ms 760 KB Output is correct
15 Correct 252 ms 768 KB Output is correct
16 Correct 281 ms 888 KB Output is correct
17 Correct 284 ms 768 KB Output is correct
18 Correct 283 ms 760 KB Output is correct
19 Correct 109 ms 888 KB Output is correct
20 Correct 109 ms 760 KB Output is correct
21 Correct 107 ms 768 KB Output is correct
22 Correct 29 ms 640 KB Output is correct
23 Correct 24 ms 640 KB Output is correct
24 Correct 65 ms 640 KB Output is correct
25 Correct 165 ms 888 KB Output is correct
26 Correct 19 ms 640 KB Output is correct
27 Correct 109 ms 888 KB Output is correct
28 Correct 23 ms 640 KB Output is correct
29 Correct 21 ms 640 KB Output is correct
30 Correct 251 ms 760 KB Output is correct
31 Correct 48 ms 640 KB Output is correct
32 Correct 22 ms 640 KB Output is correct
33 Correct 146 ms 888 KB Output is correct
34 Correct 151 ms 768 KB Output is correct
35 Correct 147 ms 760 KB Output is correct
36 Correct 32 ms 640 KB Output is correct
37 Correct 37 ms 640 KB Output is correct
38 Correct 28 ms 640 KB Output is correct
39 Correct 131 ms 888 KB Output is correct
40 Correct 188 ms 760 KB Output is correct
41 Correct 149 ms 760 KB Output is correct
42 Correct 25 ms 640 KB Output is correct
43 Correct 27 ms 640 KB Output is correct
44 Correct 29 ms 640 KB Output is correct
45 Correct 937 ms 1144 KB Output is correct
46 Execution timed out 2072 ms 3380 KB Time limit exceeded
47 Halted 0 ms 0 KB -