oj.uz

Submission #780351

# Submission time Handle Problem Language Result Execution time Memory
780351 2023-07-12T08:25:58 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 2445 ms 466068 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct lca{
    static const int LG = 24;
    vector<int> tin, tout;
    vector<pair<ll, int>> sp[LG];
    void start(int n){
        tin.resize(n), tout.resize(n);
        sp[0].reserve(n*2);
    }
    void build(){
        for (int i=1; i<LG; i++){
            sp[i].resize(sp[0].size());
            for (int j=0; j + (1 << (i-1)) < sp[0].size(); j++){
                sp[i][j] = min(sp[i-1][j], sp[i-1][j + (1 << (i-1))]);
            }
        }
    }
    int query(int a, int b){
        a = tin[a], b = tin[b];
        if (a > b) swap(a, b);
        int lg = 31 - __builtin_clz(b - a + 1);
        return min(sp[lg][a], sp[lg][b - (1<<lg) + 1]).second;
    }
    bool is_par(int p, int v){
        return tin[p] <= tin[v] && tout[v] <= tout[p];
    }
    void sort_set(vector<int> &s){
        sort(s.begin(), s.end(), [&](int a, int b){return tin[a] < tin[b];});
        s.resize(unique(s.begin(), s.end()) - s.begin());
    }
    ll get_depth(int v){
        return sp[0][tin[v]].first;
    }
} lca;

int n;
vector<vector<pair<int, int>>> g;
void dfs(int v, int p, ll d){
    lca.sp[0].emplace_back(d, v);
    lca.tin[v] = lca.sp[0].size()-1;

    for (pair<int, int> e: g[v]){
        if (e.first == p) continue;
        dfs(e.first, v, d + e.second);
        lca.sp[0].emplace_back(d, v);
    }

    lca.tout[v] = lca.sp[0].size()-1;
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    g.resize(n);
    for (int i=0; i<n-1; i++){
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }
    lca.start(n);
    dfs(0, -1, 0);
    lca.build();
}
ll solve(vector<int> &x, vector<int> &y){
    sort(x.begin(), x.end()); sort(y.begin(), y.end());
    vector<int> s = x; s.insert(s.end(), y.begin(), y.end());

    lca.sort_set(s);
    for (int i=s.size()-1; i; i--) s.push_back(lca.query(s[i], s[i-1]));
    lca.sort_set(s);

    vector<int> p(s.size());
    p[0] = -1;
    vector<int> st = {0};
    for (int i=1; i<s.size(); i++){
        while (!lca.is_par(s[st.back()], s[i])) st.pop_back();
        p[i] = st.back();
        st.push_back(i);
    }

    vector<ll> min1(s.size(), 1e18), min2(s.size(), 1e18);
    for (int i=0; i<s.size(); i++){
        bool xs = binary_search(x.begin(), x.end(), s[i]);
        if (xs) min1[i] = 0;

        bool ys = binary_search(y.begin(), y.end(), s[i]);
        if (ys) min2[i] = 0;
    }

    for (int i=s.size()-1; i; i--){
        ll dist = lca.get_depth(s[i]) - lca.get_depth(s[p[i]]);
        min1[p[i]] = min(min1[p[i]], min1[i] + dist);
        min2[p[i]] = min(min2[p[i]], min2[i] + dist);
    }

    ll result = LLONG_MAX;
    for (int i=0; i<s.size(); i++){
        result = min(result, min1[i] + min2[i]);
    }
    return result;
}
long long Query(int S, int X[], int T, int Y[]) {
    vector<int> x(S), y(T);
    copy(X, X+S, x.begin()), copy(Y, Y+T, y.begin());
    return solve(x, y);
}

Compilation message

factories.cpp: In member function 'void lca::build()':
factories.cpp:17:44: 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]
   17 |             for (int j=0; j + (1 << (i-1)) < sp[0].size(); j++){
      |                           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: In function 'll solve(std::vector<int>&, std::vector<int>&)':
factories.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i=1; i<s.size(); i++){
      |                   ~^~~~~~~~~
factories.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i=0; i<s.size(); i++){
      |                   ~^~~~~~~~~
factories.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i=0; i<s.size(); i++){
      |                   ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1064 KB Output is correct
2 Correct 848 ms 22152 KB Output is correct
3 Correct 801 ms 22120 KB Output is correct
4 Correct 818 ms 22192 KB Output is correct
5 Correct 781 ms 22484 KB Output is correct
6 Correct 604 ms 22124 KB Output is correct
7 Correct 790 ms 22088 KB Output is correct
8 Correct 748 ms 22252 KB Output is correct
9 Correct 773 ms 22376 KB Output is correct
10 Correct 605 ms 22124 KB Output is correct
11 Correct 772 ms 22012 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1098 ms 441812 KB Output is correct
3 Correct 981 ms 442608 KB Output is correct
4 Correct 851 ms 442240 KB Output is correct
5 Correct 996 ms 466068 KB Output is correct
6 Correct 1085 ms 444868 KB Output is correct
7 Correct 847 ms 107064 KB Output is correct
8 Correct 688 ms 107920 KB Output is correct
9 Correct 721 ms 110768 KB Output is correct
10 Correct 884 ms 108520 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1064 KB Output is correct
2 Correct 848 ms 22152 KB Output is correct
3 Correct 801 ms 22120 KB Output is correct
4 Correct 818 ms 22192 KB Output is correct
5 Correct 781 ms 22484 KB Output is correct
6 Correct 604 ms 22124 KB Output is correct
7 Correct 790 ms 22088 KB Output is correct
8 Correct 748 ms 22252 KB Output is correct
9 Correct 773 ms 22376 KB Output is correct
10 Correct 605 ms 22124 KB Output is correct
11 Correct 772 ms 22012 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1098 ms 441812 KB Output is correct
14 Correct 981 ms 442608 KB Output is correct
15 Correct 851 ms 442240 KB Output is correct
16 Correct 996 ms 466068 KB Output is correct
17 Correct 1085 ms 444868 KB Output is correct
18 Correct 847 ms 107064 KB Output is correct
19 Correct 688 ms 107920 KB Output is correct
20 Correct 721 ms 110768 KB Output is correct
21 Correct 884 ms 108520 KB Output is correct
22 Correct 2445 ms 432028 KB Output is correct
23 Correct 1918 ms 444148 KB Output is correct
24 Correct 2121 ms 434432 KB Output is correct
25 Correct 2021 ms 442776 KB Output is correct
26 Correct 1919 ms 430916 KB Output is correct
27 Correct 2039 ms 465132 KB Output is correct
28 Correct 1516 ms 451696 KB Output is correct
29 Correct 1755 ms 430604 KB Output is correct
30 Correct 1655 ms 429968 KB Output is correct
31 Correct 1689 ms 430556 KB Output is correct
32 Correct 1153 ms 112772 KB Output is correct
33 Correct 971 ms 109680 KB Output is correct
34 Correct 1235 ms 105140 KB Output is correct
35 Correct 1138 ms 105096 KB Output is correct
36 Correct 1161 ms 105564 KB Output is correct
37 Correct 1134 ms 105548 KB Output is correct