제출 #143830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143830		osaaateiasavtnl	공장들 (JOI14_factories)	C++14	100 / 100	5689 ms	232624 KiB

factories

#ifdef HOME
#else
#include "factories.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
const int N = 5e5 + 7, LG = 20, INF = 1e18 + 7;
vector <ii> g[N];
int h[N], l[N], r[N], to[N][LG], ptr = 0;
void dfs(int u, int p) {
    to[u][0] = p; for (int i = 1; i < LG; ++i) to[u][i] = to[to[u][i - 1]][i - 1];
    l[u] = ++ptr;
    for (auto e : g[u]) if (e.first != p) { h[e.first] = h[u] + e.second; dfs(e.first, u); }
    r[u] = ptr;
}
void Init(signed N, signed A[], signed B[], signed D[]) {
    for (int i = 0; i < N - 1; ++i) { g[A[i]].app({B[i], D[i]}); g[B[i]].app({A[i], D[i]}); }
    dfs(1, 1);
}
inline bool anc(int u, int v) { return l[u] <= l[v] && r[v] <= r[u]; }
int lca(int u, int v) {
    if (anc(u, v)) return u;
    for (int i = LG - 1; i >= 0; --i) if (!anc(to[u][i], v)) u = to[u][i];
    return to[u][0];
}
int type[N];
vector <int> g1[N];
int ans;
int bl[N][2];
void dfs1(int u) {
    bl[u][0] = bl[u][1] = INF;
    if (type[u]) bl[u][type[u] - 1] = 0;
    for (int v : g1[u]) { dfs1(v); for (int i = 0; i < 2; ++i) bl[u][i] = min(bl[u][i], bl[v][i] + h[v] - h[u]); }
    ans = min(ans, bl[u][0] + bl[u][1]);
}
bool comp(int u, int v) { return l[u] < l[v]; }
long long Query(signed S, signed X[], signed T, signed Y[]) {
    vector <int> a;
    for (int i = 0; i < S; ++i) { a.app(X[i]); type[X[i]] = 1; }
    for (int i = 0; i < T; ++i) { a.app(Y[i]); type[Y[i]] = 2; }
    sort(all(a), comp);
    int sz = a.size();
    for (int i = 0; i + 1 < sz; ++i) a.app(lca(a[i], a[i + 1]));
    sort(all(a), comp); a.resize(unique(all(a)) - a.begin());
    for (int e : a) g1[e].clear();
    for (int e : a) if (!anc(a[0], e)) { cout << "LMAO\n"; exit(1); }
    vector <int> v;
    for (int e : a) {
        while (v.size() && r[v.back()] < l[e]) v.pop_back();
        if (v.size()) g1[v.back()].app(e);
        v.app(e);
    }
    ans = INF; dfs1(a[0]);
    for (int e : a) type[e] = 0;
    return ans;
}
#ifdef HOME
signed main() {
    freopen("input.txt", "r", stdin);
    signed n, q; cin >> n >> q;
    signed a[n - 1], b[n - 1], d[n - 1];
    for (int i = 0; i < n - 1; ++i) cin >> a[i] >> b[i] >> d[i];
    Init(n, a, b, d);
    while (q--) {
        signed s, t; cin >> s >> t;
        signed a[s - 1], b[t - 1];
        for (int i = 0; i < s; ++i) cin >> a[i];
        for (int i = 0; i < t; ++i) cin >> b[i];
        cout << Query(s, a, t, b) << '\n';
    }
}
#endif

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