제출 #856987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856987		Shreyan_Paliwal	공장들 (JOI14_factories)	C++17	33 / 100	8029 ms	284804 KiB

factories

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

#define T int
#define OPERATION(a, b) min(a,b)
struct ND {
    static T ident;
    ND* ch[2] = { nullptr, nullptr };
    T v, f;
    ND() { ch[0] = ch[1] = nullptr; }
    ND(T V, T F, ND* l, ND* r) {
        v = V, f = F;
        ch[0] = l, ch[1] = r;
    }
    inline void create() {
        if (!ch[0]) {ch[0] = new ND(v, f, nullptr, nullptr);} 
        if (!ch[1]) {ch[1] = new ND(v, f, nullptr, nullptr);} 
    }
    inline void push(int l, int r) {
        v = OPERATION(v, f);
        f = ND::ident;
        if (l != r) create();
    }
    void upd(int l, int r, int L, int R, T K) {
        push(l, r);
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            v = K, f = K;
            return;
        }
        int m = (l + r) >> 1;
        ch[0]->upd(l, m, L, R, K);
        ch[1]->upd(m+1, r, L, R, K);
        v = OPERATION(ch[0]->v, ch[1]->v);
    }
    T qry(int l, int r, int L, int R) {
        push(l, r);
        if (R < l || r < L) return ND::ident;
        if (L <= l && r <= R) return v;
        int m = (l + r) >> 1;
        return OPERATION(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R));
    }
    ~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; }
};
T ND::ident = INF;
#undef T
#undef OPERATION

const int maxn = 500005;

Tree<maxn> tree;
LCA<maxn, 20> lca;
ND root1 = ND(INF, INF, nullptr, nullptr), 
   root2 = ND(INF, INF, nullptr, nullptr);
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]});
    }

    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]);
        root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], dist[X[i]]);
    }
    for (int i = 0; i < T; i++) {
        nds.push_back(Y[i]);
        root2.upd(0, tree.cnt-1, tree.st[Y[i]], 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 (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) {
        ans = min(ans, -2*dist[i] + root1.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1) + root2.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1));
    }
    for (int i = 0; i < S; i++) root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], INF);
    for (int i = 0; i < T; i++) root2.upd(0, tree.cnt-1, tree.st[Y[i]], tree.st[Y[i]], INF);
    return ans;
}

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

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:136: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]
  136 |     for (int i = 0; i < nds.size()-1; i++) v.push_back(lca(nds[i], nds[i+1]));
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67