oj.uz

Submission #857000

# Submission time Handle Problem Language Result Execution time Memory
857000 2023-10-05T07:43:34 Z Shreyan_Paliwal Factories (JOI14_factories) C++17
100 / 100
 7377 ms 227728 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;
const int maxn = 500005;

int st[maxn * 4];
void upd(int p, int l, int r, int K, int V) {
    if (p == 0) return;
    if (l == r) {st[p] = V; return;}
    int m = (l + r) >> 1;
    if (K <= m) upd(p<<1, l, m, K, V);
    else upd(p<<1|1, m+1, r, K, V);
    st[p] = min(st[p<<1], st[p<<1|1]);
}
int qry(int p, int l, int r, int L, int R) {
    if (R < l || r < L) return INF;
    if (L <= l && r <= R) return st[p];
    int m = (l + r) >> 1;
    return min(qry(p<<1, l, m, L, R), qry(p<<1|1, m+1, r, L, R));
}
int st2[maxn * 4];
void upd2(int p, int l, int r, int K, int V) {
    if (l == r) {st2[p] = V; return;}
    int m = (l + r) >> 1;
    if (K <= m) upd2(p<<1, l, m, K, V);
    else upd2(p<<1|1, m+1, r, K, V);
    st2[p] = min(st2[p<<1], st2[p<<1|1]);
}
int qry2(int p, int l, int r, int L, int R) {
    if (R < l || r < L) return INF;
    if (L <= l && r <= R) return st2[p];
    int m = (l + r) >> 1;
    return min(qry2(p<<1, l, m, L, R), qry2(p<<1|1, m+1, r, L, R));
}


Tree<maxn> tree;
LCA<maxn, 20> lca;
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]});
    }

    fill(st, st+maxn*4, INF);
    fill(st2, st2+maxn*4, INF);

    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]);
        upd(1, 0, tree.cnt-1, tree.st[X[i]], dist[X[i]]);
    }
    for (int i = 0; i < T; i++) {
        nds.push_back(Y[i]);
        upd2(1, 0, tree.cnt-1, 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 i = 0... tree.cnt-1 print queries @ [i, i] for st & st2
    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) {
        // output queries
        ans = min(ans, -2*dist[i] + qry(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1) + qry2(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1));

    }
    for (int i = 0; i < S; i++) upd(1, 0, tree.cnt-1, tree.st[X[i]], INF);
    for (int i = 0; i < T; i++) upd2(1, 0, tree.cnt-1, tree.st[Y[i]], INF);
    return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:123: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]
  123 |     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 45 ms 70232 KB Output is correct
2 Correct 1842 ms 77176 KB Output is correct
3 Correct 2004 ms 76776 KB Output is correct
4 Correct 1951 ms 76948 KB Output is correct
5 Correct 2005 ms 77184 KB Output is correct
6 Correct 1481 ms 76776 KB Output is correct
7 Correct 2020 ms 76680 KB Output is correct
8 Correct 1939 ms 77008 KB Output is correct
9 Correct 1998 ms 77336 KB Output is correct
10 Correct 1480 ms 76780 KB Output is correct
11 Correct 2004 ms 76684 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 70232 KB Output is correct
2 Correct 2529 ms 187840 KB Output is correct
3 Correct 3717 ms 190524 KB Output is correct
4 Correct 1873 ms 185668 KB Output is correct
5 Correct 3952 ms 203688 KB Output is correct
6 Correct 3992 ms 190800 KB Output is correct
7 Correct 3394 ms 101196 KB Output is correct
8 Correct 2141 ms 100464 KB Output is correct
9 Correct 3429 ms 103024 KB Output is correct
10 Correct 3367 ms 101648 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70232 KB Output is correct
2 Correct 1842 ms 77176 KB Output is correct
3 Correct 2004 ms 76776 KB Output is correct
4 Correct 1951 ms 76948 KB Output is correct
5 Correct 2005 ms 77184 KB Output is correct
6 Correct 1481 ms 76776 KB Output is correct
7 Correct 2020 ms 76680 KB Output is correct
8 Correct 1939 ms 77008 KB Output is correct
9 Correct 1998 ms 77336 KB Output is correct
10 Correct 1480 ms 76780 KB Output is correct
11 Correct 2004 ms 76684 KB Output is correct
12 Correct 14 ms 70232 KB Output is correct
13 Correct 2529 ms 187840 KB Output is correct
14 Correct 3717 ms 190524 KB Output is correct
15 Correct 1873 ms 185668 KB Output is correct
16 Correct 3952 ms 203688 KB Output is correct
17 Correct 3992 ms 190800 KB Output is correct
18 Correct 3394 ms 101196 KB Output is correct
19 Correct 2141 ms 100464 KB Output is correct
20 Correct 3429 ms 103024 KB Output is correct
21 Correct 3367 ms 101648 KB Output is correct
22 Correct 4607 ms 192120 KB Output is correct
23 Correct 4329 ms 191236 KB Output is correct
24 Correct 4861 ms 193836 KB Output is correct
25 Correct 4987 ms 194212 KB Output is correct
26 Correct 6025 ms 214024 KB Output is correct
27 Correct 5233 ms 227728 KB Output is correct
28 Correct 3306 ms 215300 KB Output is correct
29 Correct 6082 ms 213800 KB Output is correct
30 Correct 6084 ms 213492 KB Output is correct
31 Correct 7377 ms 213808 KB Output is correct
32 Correct 3077 ms 120316 KB Output is correct
33 Correct 2149 ms 117952 KB Output is correct
34 Correct 2719 ms 114152 KB Output is correct
35 Correct 2704 ms 113724 KB Output is correct
36 Correct 3114 ms 114232 KB Output is correct
37 Correct 3228 ms 114220 KB Output is correct