oj.uz

Submission #656634

# Submission time Handle Problem Language Result Execution time Memory
656634 2022-11-08T02:46:16 Z minhnhatnoe Factories (JOI14_factories) C++17
100 / 100
 3279 ms 415444 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LG = 20;
struct lcasparse{
    vector<pair<ll, int>> a[LG];
    vector<int> tin;
    vector<int> tout;
    void add_node(ll d, int v){
        if (tin[v] == -1) tin[v] = a[0].size();
        a[0].emplace_back(d, v);
    }
    void mark_out(int v){
        tout[v] = a[0].size()-1;
    }
    void lock(){
        for (int i=1; i<LG; i++){
            a[i].resize(a[0].size());
            for (int j=0; j + (1<<(i-1)) < a[i].size(); j++){
                a[i][j] = min(a[i-1][j], a[i-1][j + (1<<(i-1))]);
            }
        }
    }
    int query(int u, int v){
        if (tin[u] > tin[v]) swap(u, v);
        int lg2 = 31 - __builtin_clz(tin[v] - tin[u] + 1);
        return min(a[lg2][tin[u]], a[lg2][tin[v] - (1<<lg2) + 1]).second;
    }
    void init(int n){
        tin.resize(n, -1);
        tout.resize(n, -1);
    }
    ll get_depth(int v){
        return a[0][tin[v]].first;
    }
    bool is_par(int p, int v){
        return tin[p] <= tin[v] && tin[v] <= tout[p];
    }
} lca;
vector<vector<pair<int, ll>>> g;
void dfslca(int v, int p, ll d){
    lca.add_node(d, v);
    for (auto [u, ed]: g[v]){
        if (u == p) continue;
        dfslca(u, v, ed + d);
        lca.add_node(d, v);
    }
    lca.mark_out(v);
}
void Init(int N, int A[], int B[], int D[]){
    g.resize(N);
    for (int i=0; i<N-1; i++){
        int u = A[i], v = B[i];
        int d = D[i];
        g[u].emplace_back(v, d);
        g[v].emplace_back(u, d);
    }
    lca.init(N);
    dfslca(0, -1, 0);
    lca.lock();
}
struct testcase{
    vector<int> &from, &to;
    vector<bool> is_src;
    vector<int> nodes;
    void get_nodes(){
        for (int i=nodes.size()-1; i; i--){
            nodes.push_back(lca.query(nodes[i-1], nodes[i]));
        }
        sort(nodes.begin(), nodes.end(), [](int &a, int &b){
            return lca.tin[a] < lca.tin[b];
        });
        nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
    }
    vector<vector<pair<int, ll>>> vtr;
    void build_tree(){
        vtr.resize(nodes.size());
        // rid, vid
        vector<pair<int, int>> st;
        for (int i=0; i < nodes.size(); i++){
            int v = nodes[i];
            while (st.size() && !lca.is_par(st.back().first, v)){
                st.pop_back();
            }
            if (st.size()){
                vtr[st.back().second].emplace_back(i,
                    lca.get_depth(v) - lca.get_depth(st.back().first));
            }
            st.emplace_back(v, i);
        }
    }
    vector<ll> dp;
    void dfs1(int v, int p){
        if (is_src[v] == 1) dp[v] = 0;
        else dp[v] = 1e15;
        for (pair<int, ll> e: vtr[v]){
            assert((e.first != p));
            dfs1(e.first, v);
            dp[v] = min(dp[v], dp[e.first] + e.second);
        }
    }
    void dfs2(int v, int p){
        for (pair<int, ll> e: vtr[v]){
            dp[e.first] = min(dp[e.first], dp[v] + e.second);
            dfs2(e.first, v);
        }
    }
    ll result = LLONG_MAX;
    void mark_src(){
        sort(from.begin(), from.end(), [](int &a, int &b){
            return lca.tin[a] < lca.tin[b];
        });
        is_src.resize(nodes.size());
        for (int nptr = 0, i=0; i < from.size(); i++){
            while (nodes[nptr] != from[i]) nptr++;
            is_src[nptr] = 1;
        }
    }
    void get_result(){
        result = LLONG_MAX;
        sort(to.begin(), to.end(), [](int &a, int &b){
            return lca.tin[a] < lca.tin[b];
        });
        is_src.resize(nodes.size());
        for (int nptr = 0, i=0; i < to.size(); i++){
            while (nodes[nptr] != to[i]) nptr++;
            result = min(result, dp[nptr]);

        }
    }
    testcase(vector<int> &from, vector<int> &to): from(from), to(to) {
        nodes = to;
        for (int v: from){
            nodes.push_back(v);
        }
        sort(nodes.begin(), nodes.end(), [](int &a, int &b){
            return lca.tin[a] < lca.tin[b];
        });
        get_nodes();
        mark_src();
        build_tree();
        dp.resize(nodes.size());
        dfs1(0, -1);
        dfs2(0, -1);
        get_result();
    }
};
ll Query(int S, int X[], int T, int Y[]){
    vector<int> from(X, X + S);
    vector<int> to(Y, Y + T);
    return testcase(from, to).result;
}

Compilation message

factories.cpp: In member function 'void lcasparse::lock()':
factories.cpp:20:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             for (int j=0; j + (1<<(i-1)) < a[i].size(); j++){
      |                           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
factories.cpp: In member function 'void testcase::build_tree()':
factories.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i=0; i < nodes.size(); i++){
      |                       ~~^~~~~~~~~~~~~~
factories.cpp: In member function 'void testcase::mark_src()':
factories.cpp:115:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int nptr = 0, i=0; i < from.size(); i++){
      |                                 ~~^~~~~~~~~~~~~
factories.cpp: In member function 'void testcase::get_result()':
factories.cpp:126:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int nptr = 0, i=0; i < to.size(); i++){
      |                                 ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 980 KB Output is correct
2 Correct 950 ms 12240 KB Output is correct
3 Correct 971 ms 12212 KB Output is correct
4 Correct 942 ms 12404 KB Output is correct
5 Correct 905 ms 12724 KB Output is correct
6 Correct 612 ms 12188 KB Output is correct
7 Correct 1080 ms 12124 KB Output is correct
8 Correct 906 ms 12400 KB Output is correct
9 Correct 900 ms 12708 KB Output is correct
10 Correct 645 ms 12232 KB Output is correct
11 Correct 1004 ms 12096 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 1219 ms 367740 KB Output is correct
3 Correct 1199 ms 373436 KB Output is correct
4 Correct 982 ms 365444 KB Output is correct
5 Correct 1202 ms 415444 KB Output is correct
6 Correct 1384 ms 374472 KB Output is correct
7 Correct 1355 ms 83068 KB Output is correct
8 Correct 802 ms 82340 KB Output is correct
9 Correct 966 ms 88840 KB Output is correct
10 Correct 1327 ms 84284 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 980 KB Output is correct
2 Correct 950 ms 12240 KB Output is correct
3 Correct 971 ms 12212 KB Output is correct
4 Correct 942 ms 12404 KB Output is correct
5 Correct 905 ms 12724 KB Output is correct
6 Correct 612 ms 12188 KB Output is correct
7 Correct 1080 ms 12124 KB Output is correct
8 Correct 906 ms 12400 KB Output is correct
9 Correct 900 ms 12708 KB Output is correct
10 Correct 645 ms 12232 KB Output is correct
11 Correct 1004 ms 12096 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 1219 ms 367740 KB Output is correct
14 Correct 1199 ms 373436 KB Output is correct
15 Correct 982 ms 365444 KB Output is correct
16 Correct 1202 ms 415444 KB Output is correct
17 Correct 1384 ms 374472 KB Output is correct
18 Correct 1355 ms 83068 KB Output is correct
19 Correct 802 ms 82340 KB Output is correct
20 Correct 966 ms 88840 KB Output is correct
21 Correct 1327 ms 84284 KB Output is correct
22 Correct 2686 ms 377720 KB Output is correct
23 Correct 2323 ms 380404 KB Output is correct
24 Correct 2789 ms 383128 KB Output is correct
25 Correct 2816 ms 387684 KB Output is correct
26 Correct 2605 ms 375200 KB Output is correct
27 Correct 3279 ms 414840 KB Output is correct
28 Correct 1674 ms 376576 KB Output is correct
29 Correct 2992 ms 374456 KB Output is correct
30 Correct 2145 ms 373524 KB Output is correct
31 Correct 2560 ms 374564 KB Output is correct
32 Correct 1442 ms 95708 KB Output is correct
33 Correct 866 ms 87736 KB Output is correct
34 Correct 1257 ms 80716 KB Output is correct
35 Correct 2333 ms 80536 KB Output is correct
36 Correct 1428 ms 81712 KB Output is correct
37 Correct 1384 ms 81656 KB Output is correct