oj.uz

Submission #856987

# Submission time Handle Problem Language Result Execution time Memory
856987 2023-10-05T06:47:27 Z Shreyan_Paliwal Factories (JOI14_factories) C++17
33 / 100
 8000 ms 284804 KB 
#include "factories.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<int SZ> struct Tree {
    vector<pair<int,int>> adj[SZ];
    int st[SZ], en[SZ], cnt=0;
    void flatten(int nd, int par) {
        st[nd] = cnt++;
        for (auto i : adj[nd])
            if (i.first != par)
                flatten(i.first, nd);
        en[nd] = cnt;
    }
};

template<int SZ, int LOG> struct LCA {
    int bl[SZ][LOG];
    int dpth[SZ], st[SZ], en[SZ], cnt=0;
    Tree<SZ>* tree;
    void init_dfs(int nd, int par) {
        dpth[nd] = dpth[par]+1;
        bl[nd][0] = par;
        for (int i = 1; i < LOG; i++)
            bl[nd][i] = bl[bl[nd][i-1]][i-1];
        for (auto& i : tree->adj[nd])
            if (i.first != par)
                init_dfs(i.first, nd);
    }
    void init(Tree<SZ>* TREE, int R = 0) {
        tree = TREE;
        init_dfs(R, R);
    }
    int operator()(int a, int b) {
        if (dpth[a] > dpth[b]) swap(a, b);
        for (int i = 19; i >= 0; i--)
            if (!(tree->st[bl[b][i]] <= tree->st[a] && tree->en[a] <= tree->en[bl[b][i]]))
                b = bl[b][i];
        return bl[b][0];
    }
};

const int INF = LLONG_MAX >> 1ll;

#define T int
#define OPERATION(a, b) min(a,b)
struct ND {
    static T ident;
    ND* ch[2] = { nullptr, nullptr };
    T v, f;
    ND() { ch[0] = ch[1] = nullptr; }
    ND(T V, T F, ND* l, ND* r) {
        v = V, f = F;
        ch[0] = l, ch[1] = r;
    }
    inline void create() {
        if (!ch[0]) {ch[0] = new ND(v, f, nullptr, nullptr);} 
        if (!ch[1]) {ch[1] = new ND(v, f, nullptr, nullptr);} 
    }
    inline void push(int l, int r) {
        v = OPERATION(v, f);
        f = ND::ident;
        if (l != r) create();
    }
    void upd(int l, int r, int L, int R, T K) {
        push(l, r);
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            v = K, f = K;
            return;
        }
        int m = (l + r) >> 1;
        ch[0]->upd(l, m, L, R, K);
        ch[1]->upd(m+1, r, L, R, K);
        v = OPERATION(ch[0]->v, ch[1]->v);
    }
    T qry(int l, int r, int L, int R) {
        push(l, r);
        if (R < l || r < L) return ND::ident;
        if (L <= l && r <= R) return v;
        int m = (l + r) >> 1;
        return OPERATION(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R));
    }
    ~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; }
};
T ND::ident = INF;
#undef T
#undef OPERATION

const int maxn = 500005;

Tree<maxn> tree;
LCA<maxn, 20> lca;
ND root1 = ND(INF, INF, nullptr, nullptr), 
   root2 = ND(INF, INF, nullptr, nullptr);
int dist[maxn];

void dfs(int nd, int par) {
    for (auto i : tree.adj[nd])
        if (i.first != par) {
            dist[i.first] = dist[nd] + i.second;
            dfs(i.first, nd);
        }
}

void Init(signed N, signed A[], signed B[], signed D[]) {

    for (int i = 0; i < N-1; i++) {
        tree.adj[A[i]].push_back({B[i], D[i]});
        tree.adj[B[i]].push_back({A[i], D[i]});
    }

    tree.flatten(0, 0);

    lca.init(&tree, 0);

    dist[0] = 0;
    dfs(0, 0);
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
    vector<int> nds;
    for (int i = 0; i < S; i++) {
        nds.push_back(X[i]);
        root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], dist[X[i]]);
    }
    for (int i = 0; i < T; i++) {
        nds.push_back(Y[i]);
        root2.upd(0, tree.cnt-1, tree.st[Y[i]], tree.st[Y[i]], dist[Y[i]]);
    }
    sort(nds.begin(), nds.end(), [](int a, int b) { return tree.st[a] < tree.st[b]; });
    vector<int> v;
    for (int i = 0; i < nds.size()-1; i++) v.push_back(lca(nds[i], nds[i+1]));
    for (auto i : v) nds.push_back(i);
    sort(nds.begin(), nds.end(), [](int a, int b) { return tree.st[a] < tree.st[b]; });
    int ans = INF;
    for (auto i : nds) {
        ans = min(ans, -2*dist[i] + root1.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1) + root2.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1));
    }
    for (int i = 0; i < S; i++) root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], INF);
    for (int i = 0; i < T; i++) root2.upd(0, tree.cnt-1, tree.st[Y[i]], tree.st[Y[i]], INF);
    return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:136:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0; i < nds.size()-1; i++) v.push_back(lca(nds[i], nds[i+1]));
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 39516 KB Output is correct
2 Correct 1956 ms 58632 KB Output is correct
3 Correct 2224 ms 58360 KB Output is correct
4 Correct 2156 ms 58752 KB Output is correct
5 Correct 2194 ms 58904 KB Output is correct
6 Correct 1656 ms 58460 KB Output is correct
7 Correct 2222 ms 58360 KB Output is correct
8 Correct 2095 ms 58576 KB Output is correct
9 Correct 2214 ms 58956 KB Output is correct
10 Correct 1647 ms 58456 KB Output is correct
11 Correct 2232 ms 58196 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 39584 KB Output is correct
2 Correct 4064 ms 269340 KB Output is correct
3 Correct 6291 ms 270968 KB Output is correct
4 Correct 3146 ms 266772 KB Output is correct
5 Correct 5786 ms 284804 KB Output is correct
6 Correct 6527 ms 272252 KB Output is correct
7 Correct 5576 ms 102984 KB Output is correct
8 Correct 3314 ms 102368 KB Output is correct
9 Correct 5299 ms 105004 KB Output is correct
10 Correct 5080 ms 103636 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 39516 KB Output is correct
2 Correct 1956 ms 58632 KB Output is correct
3 Correct 2224 ms 58360 KB Output is correct
4 Correct 2156 ms 58752 KB Output is correct
5 Correct 2194 ms 58904 KB Output is correct
6 Correct 1656 ms 58460 KB Output is correct
7 Correct 2222 ms 58360 KB Output is correct
8 Correct 2095 ms 58576 KB Output is correct
9 Correct 2214 ms 58956 KB Output is correct
10 Correct 1647 ms 58456 KB Output is correct
11 Correct 2232 ms 58196 KB Output is correct
12 Correct 11 ms 39584 KB Output is correct
13 Correct 4064 ms 269340 KB Output is correct
14 Correct 6291 ms 270968 KB Output is correct
15 Correct 3146 ms 266772 KB Output is correct
16 Correct 5786 ms 284804 KB Output is correct
17 Correct 6527 ms 272252 KB Output is correct
18 Correct 5576 ms 102984 KB Output is correct
19 Correct 3314 ms 102368 KB Output is correct
20 Correct 5299 ms 105004 KB Output is correct
21 Correct 5080 ms 103636 KB Output is correct
22 Correct 7061 ms 279048 KB Output is correct
23 Correct 7157 ms 278204 KB Output is correct
24 Correct 7551 ms 280920 KB Output is correct
25 Execution timed out 8029 ms 281752 KB Time limit exceeded
26 Halted 0 ms 0 KB -