oj.uz

Submission #1096965

# Submission time Handle Problem Language Result Execution time Memory
1096965 2024-10-05T15:09:49 Z KhoaDuy Factories (JOI14_factories) C++14
100 / 100
 2364 ms 191404 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 34132 KB Output is correct
2 Correct 792 ms 52064 KB Output is correct
3 Correct 835 ms 52300 KB Output is correct
4 Correct 805 ms 52052 KB Output is correct
5 Correct 685 ms 52312 KB Output is correct
6 Correct 516 ms 52048 KB Output is correct
7 Correct 818 ms 52308 KB Output is correct
8 Correct 786 ms 52336 KB Output is correct
9 Correct 706 ms 52564 KB Output is correct
10 Correct 530 ms 52052 KB Output is correct
11 Correct 786 ms 52080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33880 KB Output is correct
2 Correct 957 ms 139888 KB Output is correct
3 Correct 1261 ms 144436 KB Output is correct
4 Correct 702 ms 137104 KB Output is correct
5 Correct 1027 ms 185368 KB Output is correct
6 Correct 1329 ms 146260 KB Output is correct
7 Correct 1012 ms 74324 KB Output is correct
8 Correct 475 ms 73780 KB Output is correct
9 Correct 606 ms 81232 KB Output is correct
10 Correct 1018 ms 76068 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 34132 KB Output is correct
2 Correct 792 ms 52064 KB Output is correct
3 Correct 835 ms 52300 KB Output is correct
4 Correct 805 ms 52052 KB Output is correct
5 Correct 685 ms 52312 KB Output is correct
6 Correct 516 ms 52048 KB Output is correct
7 Correct 818 ms 52308 KB Output is correct
8 Correct 786 ms 52336 KB Output is correct
9 Correct 706 ms 52564 KB Output is correct
10 Correct 530 ms 52052 KB Output is correct
11 Correct 786 ms 52080 KB Output is correct
12 Correct 16 ms 33880 KB Output is correct
13 Correct 957 ms 139888 KB Output is correct
14 Correct 1261 ms 144436 KB Output is correct
15 Correct 702 ms 137104 KB Output is correct
16 Correct 1027 ms 185368 KB Output is correct
17 Correct 1329 ms 146260 KB Output is correct
18 Correct 1012 ms 74324 KB Output is correct
19 Correct 475 ms 73780 KB Output is correct
20 Correct 606 ms 81232 KB Output is correct
21 Correct 1018 ms 76068 KB Output is correct
22 Correct 2216 ms 156220 KB Output is correct
23 Correct 1851 ms 157324 KB Output is correct
24 Correct 2216 ms 161524 KB Output is correct
25 Correct 2364 ms 163988 KB Output is correct
26 Correct 2225 ms 154452 KB Output is correct
27 Correct 2103 ms 191404 KB Output is correct
28 Correct 1195 ms 152236 KB Output is correct
29 Correct 2337 ms 152908 KB Output is correct
30 Correct 2259 ms 152404 KB Output is correct
31 Correct 2122 ms 152932 KB Output is correct
32 Correct 1066 ms 84164 KB Output is correct
33 Correct 793 ms 77268 KB Output is correct
34 Correct 1196 ms 72804 KB Output is correct
35 Correct 1102 ms 72780 KB Output is correct
36 Correct 1220 ms 73812 KB Output is correct
37 Correct 1229 ms 73552 KB Output is correct