제출 #1188457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188457		swishy123	공장들 (JOI14_factories)	C++20	100 / 100	4906 ms	160904 KiB

factories

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>
#include "factories.h"

using namespace std;

#ifndef template
#ifndef define
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second 
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) 
#define siz(x) (int)x.size()
 
#endif
 
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
 
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v[i].size(); j++)
            print(v[i][j]);
        nl;
    }
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
 
#endif
 
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
 
template<typename T> 
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++)
        read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector(n, args...);
    else
        return vector(n, vec(args...));
}

#endif

using namespace std;
const ll inf = 1e18;
const ll def = 5e5+1;
const ll mod = 1e9+9;

using namespace std;

vector<pi> edg[def];
ll order[def], h[def], wi[def];
int par[def], f[def][20];
int crr = 0;

void dfs(int u, int pre){
    order[u] = crr++;
    for (auto [v, w] : edg[u]){
        if (v == pre)
            continue;
        par[v] = u;
        wi[v] = wi[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if (h[v] < h[u]) swap(u, v);
    for (int i = 19; i >= 0; i--){
        if (f[v][i] != -1 && h[f[v][i]] >= h[u])
            v = f[v][i];
    }    
    if (u == v) return u;
    for (int i = 19; i >= 0; i--){
        if (f[v][i] != -1 && f[u][i] != -1 && f[v][i] != f[u][i])
            u = f[u][i], v = f[v][i];
    }
    return par[u];
}

void Init(int N, int A[], int B[], int D[]){
    for (int i = 0; i < N - 1; i++){
        edg[A[i]].push_back({B[i], D[i]});
        edg[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, -1);
    for (int i = 0; i < N; i++) for (int j = 0; j < 20; j++)
        f[i][j] = -1;
    for (int i = 0; i < N; i++)
        f[i][0] = par[i];
    for (int j = 1; j < 20; j++){
        for (int i = 0; i < N; i++){
            int p = f[i][j - 1];
            if (p != -1)
                f[i][j] = f[p][j - 1];
        }
    }
}

vector<pl> edg2[def];
bool inA[def], inB[def];
ll dp[def], res = inf;

void dfs2(int u, int pre){
    if (inB[u])
        dp[u] = 0;
    for (auto [v, w] : edg2[u]){
        if (v == pre)
            continue;
        dfs2(v, u);
        mini(dp[u], dp[v] + w);
    }
}

void dfs3(int u, int pre, ll crr){
    if (inB[u])
        crr = 0;
    vector<pl> child;
    for (auto [v, w] : edg2[u]){
        if (v == pre)
            continue;
        child.push_back({v, w});
    }
    int m = child.size();
    auto pref = vec(m + 1, inf);
    auto suff = pref;

    for (int i = 1; i <= m; i++){
        auto [v, w] = child[i - 1];
        pref[i] = min(pref[i - 1], dp[v] + w);
    }
    for (int i = m - 1; i >= 0; i--){
        auto [v, w] = child[i];
        suff[i] = min(suff[i + 1], dp[v] + w);
    }
    for (int i = 0; i < m; i++){
        auto [v, w] = child[i];
        dfs3(v, u, min({pref[i], suff[i + 1], crr}) + w);
    }   
    if (inA[u])
        mini(res, min(crr, dp[u]));
}

long long Query(int S, int X[], int T, int Y[]){
    vector<int> nodes;
    for (int i = 0; i < S; i++){
        nodes.push_back(X[i]);
        inA[X[i]] = 1;
    }
    for (int i = 0; i < T; i++){
        nodes.push_back(Y[i]);
        inB[Y[i]] = 1;
    }
    sort(nodes.begin(), nodes.end(), [](int a, int b){
        return order[a] < order[b];
    });
    int m = nodes.size();
    for (int i = 1; i < m; i++){
        int p = lca(nodes[i - 1], nodes[i]);
        nodes.push_back(p);
    }
    sort(nodes.begin(), nodes.end(), [](int a, int b){
        return order[a] < order[b];
    });
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    for (int i = 1; i < nodes.size(); i++){
        dp[nodes[i]] = dp[nodes[i - 1]] = inf;
        ll u = nodes[i], v = lca(u, nodes[i - 1]), w = wi[u] - wi[v];

        edg2[u].push_back({v, w});
        edg2[v].push_back({u, w});
    }
    int root = nodes[0]; res = inf;
    dfs2(root, -1);
    dfs3(root, -1, inf);
    for (int i = 0; i < nodes.size(); i++){
        int u = nodes[i];
        edg2[u].clear();
        inA[u] = inB[u] = 0;
    }
    return res;
}

void solve(){
    int n, q;
    read(n, q);

    int A[n - 1], B[n - 1], D[n - 1];
    for (int i = 0; i < n - 1; i++)
        read(A[i], B[i], D[i]);
    Init(n, A, B, D);   

    while (q--){
        int S, T;
        read(S, T);

        int X[S], Y[T];
        for (int i = 0; i < S; i++)
            read(X[i]);
        for (int i = 0; i < T; i++)
            read(Y[i]);
        print(Query(S, X, T, Y)); nl;
    }
}

// int32_t main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);

//     if (ifstream("input.txt").good()){
//         freopen("input.txt", "r", stdin);
//         freopen("output.txt", "w", stdout);
//     }

//     int t = 1;
//     while (t--){
//         solve();
//         nl;
//     }

//     return 0;
// }

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