제출 #780342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780342		vjudge1	공장들 (JOI14_factories)	C++17	0 / 100	5 ms	1748 KiB

factories

#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+S, y.begin());
    return solve(x, y);
}

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

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