Submission #1096965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096965		KhoaDuy	Factories (JOI14_factories)	C++14	100 / 100	2364 ms	191404 KiB

factories

#ifndef mikevui
    #include "factories.h"
#endif // mikevui
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
//#define int long long 
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
 
template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}
 
const int maxn = 5e5+5, lg = 20;
const ll INF = 3e18;
int n;
vector<pair<int, ll>> a[maxn];
int tin[maxn], tout[maxn], timer = 0, par[maxn][lg+1];
ll dis[maxn];
//virtual tree
vector<pair<int, ll>> adj[maxn];
int c[maxn];
ll mi1[maxn], mi2[maxn], ans = LLONG_MAX;
 
bool cmp(int u, int v) {
    return tin[u] < tin[v];
}
 
void dfspre(int u, int p) {
    tin[u] = ++timer;
    for (int j = 1; j <= lg; j++) {
        par[u][j] = par[par[u][j-1]][j-1];
    }
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        ll w = a[u][i].se;
        if (v == p) continue;
        dis[v] = dis[u]+w;
        par[v][0] = u;
        dfspre(v, u);
    }
    tout[u] = timer;
}
bool inside(int u, int v) {
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v) {
    if (inside(u, v)) return v;
    if (inside(v, u)) return u;
    for (int j = lg; j >= 0; j--) {
        while (par[u][j] > 0 && !inside(par[u][j], v)) {
            u = par[u][j];
        }
    }
    return par[u][0];
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n-1; i++) {
        int u = A[i]+1, v = B[i]+1;
        ll w = D[i];
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    dis[1] = 0;
    dfspre(1, -1);
    memset(mi1, 0x3f, sizeof(mi1));
    memset(mi2, 0x3f, sizeof(mi2));
    memset(c, 0, sizeof(c));
}
 
void dfsup(int u) {
    if (c[u] == 1) {
        mi1[u] = 0;
    }
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        ll w = adj[u][i].se;
        dfsup(v);
        if (mi1[v] >= INF) continue;
        ll val = mi1[v]+w;
        if (val < mi1[u]) {
            mi2[u] = mi1[u];
            mi1[u] = val;
        }
        else if (val < mi2[u]) {
            mi2[u] = val;
        }
        if (c[u] == 2){
            minimize(ans, val);
        }
    }
}
void dfsdown(int u, ll down) {
    if (c[u] == 2 && down < INF) {
        minimize(ans, down);
    }
//    cout << u << ' ' << down << "\n";
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int v = adj[u][i].fi;
        ll w = adj[u][i].se;
        ll val = min(down, (mi1[v] < INF && mi1[v]+w == mi1[u] ? mi2[u] : mi1[u]));
        if (val < INF) val += w;
        dfsdown(v, val);
    }
}
 
long long Query(int S, int X[], int T, int Y[]){
    ans = INF;
    //build virtual tree
    vector<int> nodes;
    for (int i = 0; i < S; i++) {
        int u = X[i]+1;
        nodes.push_back(u);
        c[u] = 1;
    }
    for (int i = 0; i < T; i++) {
        int u = Y[i]+1;
        nodes.push_back(u);
        if (c[u] == 1) {
            return 0LL;
        }
        c[u] = 2;
    }
    sort(nodes.begin(), nodes.end(), cmp);
    int k = nodes.size();
    for (int i = 1; i < k; i++) {
        nodes.push_back(lca(nodes[i], nodes[i-1]));
    }
    sort(nodes.begin(), nodes.end(), cmp);
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    k = nodes.size();
    vector<int> st;
    st.pb(nodes[0]); //root
    for (int i = 1; i < k; i++) {
        while (!inside(st.back(), nodes[i])) st.pop_back();
        int u = st.back(), v = nodes[i];
        adj[u].pb({v, dis[v]-dis[u]});
        st.push_back(v);
//        cout << u << ' ' << v << ' ' << dis[v]-dis[u] << "\n";
    }
    //solve, up and down
    dfsup(nodes[0]);
//    for (int i = 0; i < k; i++) {
//        cout << nodes[i] << ' ' << mi1[nodes[i]] << ' ' << mi2[nodes[i]] << "\n";
//    }
    dfsdown(nodes[0], INF);
    //reset
    for (int i = 0; i < k; i++) {
        int u = nodes[i];
        adj[u].clear();
        c[u] = 0;
        mi1[u] = mi2[u] = INF;
    }
    return ans;
}
 
int N, Q, A[maxn], B[maxn], D[maxn], S, T, X[maxn], Y[maxn];
 
#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> N >> Q;
    for (int i = 0; i < N-1; i++) {
        cin >> A[i] >> B[i] >> D[i];
    }
    Init(N, A, B, D);
    while (Q--) {
        cin >> S >> T;
        for (int i = 0; i < S; i++) {
            cin >> X[i];
        }
        for (int i = 0; i < T; i++) {
            cin >> Y[i];
        }
        cout << Query(S, X, T, Y) << "\n";
    }
}
#endif // mikevui
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
 
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
*/
 

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