oj.uz

Submission #680519

# Submission time Handle Problem Language Result Execution time Memory
680519 2023-01-11T04:30:14 Z whqkrtk04 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 190808 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }

class segtree {
    private:
    int n;
    vector<int> modi, chk;
    vector<ll> seg, lazy, dep;
    void upd_node(int i) {
        if(!chk[i]) {
            chk[i] = 1;
            modi.push_back(i);
        }
    }

    void init(int i, int s, int e, vector<ll> &B) {
        seg[i] = lazy[i] = LLINF;
        chk[i] = 0;
        if(s+1 == e) dep[i] = B[s];
        else {
            init(i<<1, s, s+e>>1, B);
            init(i<<1|1, s+e>>1, e, B);
            dep[i] = max(dep[i<<1], dep[i<<1|1]);
        }
    }

    void prop(int i, int s, int e) {
        if(s+1 < e && lazy[i] < LLINF) {
            upd_node(i<<1);
            lazy[i<<1] = min(lazy[i<<1], lazy[i]);
            seg[i<<1] = min(seg[i<<1], lazy[i]-2*dep[i<<1]);
            upd_node(i<<1|1);
            lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
            seg[i<<1|1] = min(seg[i<<1|1], lazy[i]-2*dep[i<<1|1]);
        }
        lazy[i] = LLINF;
    }

    void update(int i, int s, int e, int l, int r, ll x){
        prop(i, s, e);
        if(r <= s || e <= l) return;
        upd_node(i);
        if(l <= s && e <= r) {
            lazy[i] = min(lazy[i], x);
            seg[i] = min(seg[i], x-2*dep[i]);
        } else {
            update(i<<1, s, s+e>>1, l, r, x);
            update(i<<1|1, s+e>>1, e, l, r, x);
            seg[i] = min(seg[i<<1], seg[i<<1|1]);
        }
    }

    ll query(int i, int s, int e, int l, int r) {
        prop(i, s, e);
        if(r <= s || e <= l) return LLINF;
        if(l <= s && e <= r) return seg[i];
        return min(query(i<<1, s, s+e>>1, l, r), query(i<<1|1, s+e>>1, e, l, r));
    }

    public:
    segtree() {}
    segtree(vector<ll> &B) {
        n = B.size();
        seg.resize(4*n);
        lazy.resize(4*n);
        dep.resize(4*n);
        chk.resize(4*n);
        init(1, 0, n, B);
    }

    void update(int l, int r, ll x) { update(1, 0, n, l, r, x); }
    ll query(int l, int r) { return query(1, 0, n, l, r); }

    void clear() {
        for(auto i : modi) {
            seg[i] = lazy[i] = LLINF;
            chk[i] = 0;
        }
        modi.clear();
    }
};

class HLD {
private:
    vector<vector<int>> adj;
    vector<int> in, sz, par, top, depth;
    void traverse1(int u) {
        sz[u] = 1;
        for (int &v: adj[u]) {
            adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
            depth[v] = depth[u] + 1;
            traverse1(v);
            par[v] = u;
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
        }
    }
    void traverse2(int u) {
        static int n = 0;
        in[u] = n++;
        for (int v: adj[u]) {
            top[v] = (v == adj[u][0] ? top[u] : v);
            traverse2(v);
        }
    }
public:
    void link(int u, int v) { // u and v is 1-based
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void init() { // have to call after linking
        top[1] = 1;
        traverse1(1);
        traverse2(1);
    }
    // u is 1-based and returns dfs-order [s, e) 0-based index
    pii subtree(int u) {
        return {in[u], in[u] + sz[u]};
    }
    // u and v is 1-based and returns array of dfs-order [s, e) 0-based index
    vector<pii> path(int u, int v) {
        vector<pii> res;
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            res.emplace_back(in[top[u]], in[u] + 1);
            u = par[top[u]];
        }
        res.emplace_back(min(in[u], in[v]), max(in[u], in[v]) + 1);
        return res;
    }
    HLD() {}
    HLD(int n) { // n is number of vertexes
        adj.resize(n+1); depth.resize(n+1);
        in.resize(n+1); sz.resize(n+1);
        par.resize(n+1); top.resize(n+1);
    }
};

void dfs(int x, ll d, vector<ll> &dep, vector<bool> &vis, vector<vector<pii>> &E) {
    if(vis[x]) return;
    vis[x] = true;
    dep[x] = d;
    for(auto i : E[x]) dfs(i.fi, d+i.se, dep, vis, E);
}

segtree seg;
HLD hld;
vector<ll> dep;

void Init(int N, int A[], int B[], int D[]) {
    hld = HLD(N);
    vector<vector<pii>> E(N);
    for(int i = 0; i < N-1; i++) {
        E[A[i]].push_back({B[i], D[i]});
        E[B[i]].push_back({A[i], D[i]});
        hld.link(A[i]+1, B[i]+1);
    }
    hld.init();
    dep.resize(N);
    vector<bool> vis(N, false);
    dfs(0, 0LL, dep, vis, E);
    vector<ll> ord_dep(N);
    for(int i = 0; i < N; i++) ord_dep[hld.subtree(i+1).fi] = dep[i];
    seg = segtree(ord_dep);
}

ll Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < T; i++) {
        vector<pii> path = hld.path(1, Y[i]+1);
        for(auto j : path) seg.update(j.fi, j.se, dep[Y[i]]);
    }
    ll ans = LLINF;
    for(int i = 0; i < S; i++) {
        vector<pii> path = hld.path(1, X[i]+1);
        for(auto j : path) ans = min(ans, seg.query(j.fi, j.se)+dep[X[i]]);
    }
    seg.clear();
    return ans;
}

Compilation message

factories.cpp: In member function 'void segtree::init(int, int, int, std::vector<long long int>&)':
factories.cpp:36:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             init(i<<1, s, s+e>>1, B);
      |                           ~^~
factories.cpp:37:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |             init(i<<1|1, s+e>>1, e, B);
      |                          ~^~
factories.cpp: In member function 'void segtree::update(int, int, int, int, int, ll)':
factories.cpp:62:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |             update(i<<1, s, s+e>>1, l, r, x);
      |                             ~^~
factories.cpp:63:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |             update(i<<1|1, s+e>>1, e, l, r, x);
      |                            ~^~
factories.cpp: In member function 'll segtree::query(int, int, int, int, int)':
factories.cpp:72:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         return min(query(i<<1, s, s+e>>1, l, r), query(i<<1|1, s+e>>1, e, l, r));
      |                                   ~^~
factories.cpp:72:65: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         return min(query(i<<1, s, s+e>>1, l, r), query(i<<1|1, s+e>>1, e, l, r));
      |                                                                ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 724 KB Output is correct
2 Correct 2285 ms 19104 KB Output is correct
3 Correct 2195 ms 19116 KB Output is correct
4 Correct 2199 ms 19364 KB Output is correct
5 Correct 1037 ms 19520 KB Output is correct
6 Correct 1295 ms 19152 KB Output is correct
7 Correct 2128 ms 19192 KB Output is correct
8 Correct 1837 ms 19112 KB Output is correct
9 Correct 1010 ms 19516 KB Output is correct
10 Correct 1259 ms 19160 KB Output is correct
11 Correct 1996 ms 19260 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5047 ms 160868 KB Output is correct
3 Correct 3759 ms 162620 KB Output is correct
4 Correct 2337 ms 162676 KB Output is correct
5 Correct 2783 ms 190808 KB Output is correct
6 Correct 4088 ms 163692 KB Output is correct
7 Correct 3663 ms 50464 KB Output is correct
8 Correct 2106 ms 50684 KB Output is correct
9 Correct 2960 ms 53644 KB Output is correct
10 Correct 3717 ms 50756 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 724 KB Output is correct
2 Correct 2285 ms 19104 KB Output is correct
3 Correct 2195 ms 19116 KB Output is correct
4 Correct 2199 ms 19364 KB Output is correct
5 Correct 1037 ms 19520 KB Output is correct
6 Correct 1295 ms 19152 KB Output is correct
7 Correct 2128 ms 19192 KB Output is correct
8 Correct 1837 ms 19112 KB Output is correct
9 Correct 1010 ms 19516 KB Output is correct
10 Correct 1259 ms 19160 KB Output is correct
11 Correct 1996 ms 19260 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 5047 ms 160868 KB Output is correct
14 Correct 3759 ms 162620 KB Output is correct
15 Correct 2337 ms 162676 KB Output is correct
16 Correct 2783 ms 190808 KB Output is correct
17 Correct 4088 ms 163692 KB Output is correct
18 Correct 3663 ms 50464 KB Output is correct
19 Correct 2106 ms 50684 KB Output is correct
20 Correct 2960 ms 53644 KB Output is correct
21 Correct 3717 ms 50756 KB Output is correct
22 Execution timed out 8069 ms 169216 KB Time limit exceeded
23 Halted 0 ms 0 KB -