제출 #656634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656634		minhnhatnoe	공장들 (JOI14_factories)	C++17	100 / 100	3279 ms	415444 KiB

factories

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67