oj.uz

Submission #977665

# Submission time Handle Problem Language Result Execution time Memory
977665 2024-05-08T08:48:57 Z LOLOLO Factories (JOI14_factories) C++17
100 / 100
 2899 ms 182176 KB 
#include "factories.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 5e5 + 100;
vector <pair <int, int>> ed[N];
vector <pair <int, ll>> ed2[N];

int in[N], ou[N], p[N][20], timer = 1, col[N];
ll dep[N], f1[N], f2[N];

void dfs(int u, int v) {
    p[u][0] = v;
    for (int j = 1; j < 20; j++)
        p[u][j] = p[p[u][j - 1]][j - 1];

    in[u] = ++timer;
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        dep[x.f] = dep[u] + x.s;
        dfs(x.f, u);
    }

    ou[u] = timer;
}

int is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b];
}

int lca(int a, int b) {
    if (is(a, b))
        return a;

    if (is(b, a))
        return b;

    for (int j = 19; j >= 0; j--) {
        if (is(p[a][j], b) == 0)
            a = p[a][j];
    }

    return p[a][0];
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 1; i <= N; i++) {
        f1[i] = f2[i] = 1e16;
    }

    for (int i = 0; i < N - 1; i++) {
        A[i]++, B[i]++;
        ed[A[i]].pb({B[i], D[i]});
        ed[B[i]].pb({A[i], D[i]});
    }

    dfs(1, 1);
}

void dfs2(int u) {
    if (col[u] == 1) {
        f1[u] = 0;
    }

    if (col[u] == 2) {
        f2[u] = 0;
    }

    for (auto x : ed2[u]) {
        dfs2(x.f);
        f1[u] = min(f1[u], f1[x.f] + x.s);
        f2[u] = min(f2[u], f2[x.f] + x.s);
    }
} 

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> node;
    for (int i = 0; i < S; i++) {
        X[i]++;
        node.pb(X[i]);
        col[X[i]] = 2;
    }

    for (int i = 0; i < T; i++) {
        Y[i]++;
        node.pb(Y[i]);
        col[Y[i]] = 1;
    }

    sort(all(node), [&](int a, int b) {return in[a] < in[b];});
    for (int i = 0; i < S + T - 1; i++) {
        node.pb({lca(node[i], node[i + 1])});
    }

    node.pb(1);
    uniquev(node);
    sort(all(node), [&] (int a, int b) {return in[a] < in[b];});

    stack <int> st;
    for (auto x : node) {
        if (sz(st)) {
            while (is(st.top(), x) == 0)
                st.pop();

            ed2[st.top()].pb({x, dep[x] - dep[st.top()]});
        }
        st.push(x);
    }

    dfs2(1);

    ll ans = 1e16;
    for (auto x : node) {
        ans = min(ans, f1[x] + f2[x]);
        f1[x] = f2[x] = 1e16;
        col[x] = 0;
        ed2[x].clear();
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 51536 KB Output is correct
2 Correct 826 ms 56288 KB Output is correct
3 Correct 831 ms 56304 KB Output is correct
4 Correct 805 ms 56348 KB Output is correct
5 Correct 589 ms 56404 KB Output is correct
6 Correct 746 ms 56240 KB Output is correct
7 Correct 802 ms 56512 KB Output is correct
8 Correct 780 ms 56384 KB Output is correct
9 Correct 588 ms 56656 KB Output is correct
10 Correct 707 ms 56312 KB Output is correct
11 Correct 806 ms 56308 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51548 KB Output is correct
2 Correct 1221 ms 122928 KB Output is correct
3 Correct 1656 ms 145336 KB Output is correct
4 Correct 993 ms 141640 KB Output is correct
5 Correct 1255 ms 177940 KB Output is correct
6 Correct 1781 ms 146220 KB Output is correct
7 Correct 1367 ms 90468 KB Output is correct
8 Correct 785 ms 89820 KB Output is correct
9 Correct 626 ms 95892 KB Output is correct
10 Correct 1219 ms 91296 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 51536 KB Output is correct
2 Correct 826 ms 56288 KB Output is correct
3 Correct 831 ms 56304 KB Output is correct
4 Correct 805 ms 56348 KB Output is correct
5 Correct 589 ms 56404 KB Output is correct
6 Correct 746 ms 56240 KB Output is correct
7 Correct 802 ms 56512 KB Output is correct
8 Correct 780 ms 56384 KB Output is correct
9 Correct 588 ms 56656 KB Output is correct
10 Correct 707 ms 56312 KB Output is correct
11 Correct 806 ms 56308 KB Output is correct
12 Correct 11 ms 51548 KB Output is correct
13 Correct 1221 ms 122928 KB Output is correct
14 Correct 1656 ms 145336 KB Output is correct
15 Correct 993 ms 141640 KB Output is correct
16 Correct 1255 ms 177940 KB Output is correct
17 Correct 1781 ms 146220 KB Output is correct
18 Correct 1367 ms 90468 KB Output is correct
19 Correct 785 ms 89820 KB Output is correct
20 Correct 626 ms 95892 KB Output is correct
21 Correct 1219 ms 91296 KB Output is correct
22 Correct 2407 ms 155292 KB Output is correct
23 Correct 2160 ms 155336 KB Output is correct
24 Correct 2766 ms 159724 KB Output is correct
25 Correct 2643 ms 161728 KB Output is correct
26 Correct 2782 ms 153156 KB Output is correct
27 Correct 1936 ms 182176 KB Output is correct
28 Correct 1661 ms 152996 KB Output is correct
29 Correct 2801 ms 151940 KB Output is correct
30 Correct 2632 ms 151500 KB Output is correct
31 Correct 2899 ms 151508 KB Output is correct
32 Correct 955 ms 97856 KB Output is correct
33 Correct 1037 ms 92240 KB Output is correct
34 Correct 1233 ms 90084 KB Output is correct
35 Correct 1205 ms 90068 KB Output is correct
36 Correct 1585 ms 90620 KB Output is correct
37 Correct 1453 ms 90964 KB Output is correct