제출 #857000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857000		Shreyan_Paliwal	공장들 (JOI14_factories)	C++17	100 / 100	7377 ms	227728 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;
const int maxn = 500005;

int st[maxn * 4];
void upd(int p, int l, int r, int K, int V) {
    if (p == 0) return;
    if (l == r) {st[p] = V; return;}
    int m = (l + r) >> 1;
    if (K <= m) upd(p<<1, l, m, K, V);
    else upd(p<<1|1, m+1, r, K, V);
    st[p] = min(st[p<<1], st[p<<1|1]);
}
int qry(int p, int l, int r, int L, int R) {
    if (R < l || r < L) return INF;
    if (L <= l && r <= R) return st[p];
    int m = (l + r) >> 1;
    return min(qry(p<<1, l, m, L, R), qry(p<<1|1, m+1, r, L, R));
}
int st2[maxn * 4];
void upd2(int p, int l, int r, int K, int V) {
    if (l == r) {st2[p] = V; return;}
    int m = (l + r) >> 1;
    if (K <= m) upd2(p<<1, l, m, K, V);
    else upd2(p<<1|1, m+1, r, K, V);
    st2[p] = min(st2[p<<1], st2[p<<1|1]);
}
int qry2(int p, int l, int r, int L, int R) {
    if (R < l || r < L) return INF;
    if (L <= l && r <= R) return st2[p];
    int m = (l + r) >> 1;
    return min(qry2(p<<1, l, m, L, R), qry2(p<<1|1, m+1, r, L, R));
}


Tree<maxn> tree;
LCA<maxn, 20> lca;
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]});
    }

    fill(st, st+maxn*4, INF);
    fill(st2, st2+maxn*4, INF);

    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]);
        upd(1, 0, tree.cnt-1, tree.st[X[i]], dist[X[i]]);
    }
    for (int i = 0; i < T; i++) {
        nds.push_back(Y[i]);
        upd2(1, 0, tree.cnt-1, 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 i = 0... tree.cnt-1 print queries @ [i, i] for st & st2
    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) {
        // output queries
        ans = min(ans, -2*dist[i] + qry(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1) + qry2(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1));

    }
    for (int i = 0; i < S; i++) upd(1, 0, tree.cnt-1, tree.st[X[i]], INF);
    for (int i = 0; i < T; i++) upd2(1, 0, tree.cnt-1, tree.st[Y[i]], INF);
    return ans;
}

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

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:123: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]
  123 |     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: 67 / 67