oj.uz

Submission #367187

# Submission time Handle Problem Language Result Execution time Memory
367187 2021-02-16T13:05:25 Z parsabahrami Factories (JOI14_factories) C++17
100 / 100
 7912 ms 161612 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

#define SZ(x)                   (int) x.size()
#define F                       first
#define S                       second

const int N = 5e5 + 10;
int M[N], from[N], to[N], w[N], P[20][N], H[N], St[N], Ft[N], n, tim; vector<int> adj[N]; ll S[N], dp1[N], dp2[N];

void preDFS(int v, int p = -1) {
    St[v] = tim++;
    for (int i = 1; i < 20; i++) 
        P[i][v] = P[i - 1][P[i - 1][v]];
    for (int id : adj[v]) {
        int u = from[id] ^ to[id] ^ v;
        if (u != p) S[u] = S[v] + w[id], H[u] = H[v] + 1, P[0][u] = v, preDFS(u, v);
    }
    Ft[v] = tim;
}

int getpar(int v, int h) {
    for (int i = h; i; i -= i & -i) 
        v = P[__builtin_ctz(i)][v];
    return v;
}

int LCA(int v, int u) {
    if (H[u] < H[v]) swap(u, v);
    u = getpar(u, H[u] - H[v]);
    for (int i = 19; ~i; i--) 
        if (P[i][v] != P[i][u]) 
            u = P[i][u], v = P[i][v];
    return u == v ? v : P[0][v];
}

void downDFS(int v) { 
    if (M[v]) dp1[v] = 0;
    for (int u : adj[v]) {
        downDFS(u);
        if (dp1[u] < 1e18) dp1[v] = min(dp1[v], dp1[u] + S[u] - S[v]);
    }
}

void upd(pair<pair<ll, ll>, pair<ll, ll>> &x, ll v, ll y) {
    x.S = min(x.S, {y, v});
    if (x.F > x.S) swap(x.S, x.F);
}

void upDFS(int v) {
    if (M[v]) dp2[v] = 0;
    pair<pair<ll, ll>, pair<ll, ll>> x = {{1e16, 1e16}, {1e16, 1e16}};
    upd(x, v, dp2[v]); 
    for (int u : adj[v]) {
        upd(x, u, dp1[u] + S[u] - S[v]);
    }
    for (int u : adj[v]) {
        if (x.F.S == u) dp2[u] = x.S.F + S[u] - S[v];
        else dp2[u] = x.F.F + S[u] - S[v];
        dp2[u] = min(dp2[u], (ll) 1e18);
    }
    for (int u : adj[v]) upDFS(u);
}   

void Init(int _n, int A[], int B[], int D[]) {
    n = _n;
    for (int i = 0; i + 1 < n; i++) {
        from[i] = A[i], to[i] = B[i], w[i] = D[i];
        adj[from[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    preDFS(0);
    for (int i = 0; i < n; i++) adj[i] = {};
    for (int i = 0; i < n; i++) dp1[i] = dp2[i] = 1e18;
}

ll Query(int s, int X[], int t, int Y[]) {
    vector<int> vec;
    for (int i = 0; i < s; i++) vec.push_back(X[i]);
    for (int i = 0; i < t; i++) vec.push_back(Y[i]), M[Y[i]] = 1;
    sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
    int k = SZ(vec);
    for (int i = 0; i < k; i++) {
        int p = LCA(vec[i], vec[(i + 1) % k]);
        vec.push_back(p);
    }
    sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    vector<int> st = {vec[0]};
    for (int i = 1; i < SZ(vec); i++) {
        int v = vec[i];
        while (St[st.back()] > St[v] || Ft[v] > Ft[st.back()]) 
            st.pop_back();
        assert(SZ(st));
        adj[st.back()].push_back(v);
        st.push_back(v);
    }   
    downDFS(vec[0]);
    upDFS(vec[0]);
    ll ret = 1e18;
    for (int i = 0; i < s; i++) ret = min(ret, min(dp1[X[i]], dp2[X[i]]));
    for (int i = 0; i < SZ(vec); i++) dp1[vec[i]] = dp2[vec[i]] = 1e18, adj[vec[i]] = {};
    for (int i = 0; i < t; i++) M[Y[i]] = 0;
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12908 KB Output is correct
2 Correct 1345 ms 30984 KB Output is correct
3 Correct 1425 ms 30712 KB Output is correct
4 Correct 1398 ms 31028 KB Output is correct
5 Correct 1332 ms 31084 KB Output is correct
6 Correct 978 ms 30940 KB Output is correct
7 Correct 1420 ms 30692 KB Output is correct
8 Correct 1343 ms 30812 KB Output is correct
9 Correct 1341 ms 31084 KB Output is correct
10 Correct 984 ms 30760 KB Output is correct
11 Correct 1430 ms 30836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12524 KB Output is correct
2 Correct 4075 ms 124336 KB Output is correct
3 Correct 4713 ms 126188 KB Output is correct
4 Correct 3195 ms 125608 KB Output is correct
5 Correct 4825 ms 157860 KB Output is correct
6 Correct 4965 ms 128196 KB Output is correct
7 Correct 5537 ms 53712 KB Output is correct
8 Correct 3493 ms 54472 KB Output is correct
9 Correct 4745 ms 58588 KB Output is correct
10 Correct 5317 ms 54872 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12908 KB Output is correct
2 Correct 1345 ms 30984 KB Output is correct
3 Correct 1425 ms 30712 KB Output is correct
4 Correct 1398 ms 31028 KB Output is correct
5 Correct 1332 ms 31084 KB Output is correct
6 Correct 978 ms 30940 KB Output is correct
7 Correct 1420 ms 30692 KB Output is correct
8 Correct 1343 ms 30812 KB Output is correct
9 Correct 1341 ms 31084 KB Output is correct
10 Correct 984 ms 30760 KB Output is correct
11 Correct 1430 ms 30836 KB Output is correct
12 Correct 12 ms 12524 KB Output is correct
13 Correct 4075 ms 124336 KB Output is correct
14 Correct 4713 ms 126188 KB Output is correct
15 Correct 3195 ms 125608 KB Output is correct
16 Correct 4825 ms 157860 KB Output is correct
17 Correct 4965 ms 128196 KB Output is correct
18 Correct 5537 ms 53712 KB Output is correct
19 Correct 3493 ms 54472 KB Output is correct
20 Correct 4745 ms 58588 KB Output is correct
21 Correct 5317 ms 54872 KB Output is correct
22 Correct 7134 ms 133172 KB Output is correct
23 Correct 6770 ms 135404 KB Output is correct
24 Correct 7602 ms 136260 KB Output is correct
25 Correct 7604 ms 138688 KB Output is correct
26 Correct 7684 ms 134364 KB Output is correct
27 Correct 7656 ms 161612 KB Output is correct
28 Correct 5305 ms 136928 KB Output is correct
29 Correct 7912 ms 134256 KB Output is correct
30 Correct 7843 ms 133260 KB Output is correct
31 Correct 7808 ms 134588 KB Output is correct
32 Correct 4772 ms 60456 KB Output is correct
33 Correct 3418 ms 55920 KB Output is correct
34 Correct 4920 ms 51436 KB Output is correct
35 Correct 4880 ms 51308 KB Output is correct
36 Correct 5079 ms 51808 KB Output is correct
37 Correct 5095 ms 52204 KB Output is correct