oj.uz

Submission #977663

# Submission time Handle Problem Language Result Execution time Memory
977663 2024-05-08T08:48:21 Z LOLOLO Factories (JOI14_factories) C++17
15 / 100
 831 ms 96200 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 = 2e5 + 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 27 ms 33372 KB Output is correct
2 Correct 831 ms 47268 KB Output is correct
3 Correct 809 ms 47184 KB Output is correct
4 Correct 770 ms 47188 KB Output is correct
5 Correct 586 ms 47436 KB Output is correct
6 Correct 698 ms 47360 KB Output is correct
7 Correct 800 ms 47436 KB Output is correct
8 Correct 778 ms 47360 KB Output is correct
9 Correct 592 ms 47696 KB Output is correct
10 Correct 694 ms 47184 KB Output is correct
11 Correct 803 ms 47184 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Runtime error 273 ms 96200 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33372 KB Output is correct
2 Correct 831 ms 47268 KB Output is correct
3 Correct 809 ms 47184 KB Output is correct
4 Correct 770 ms 47188 KB Output is correct
5 Correct 586 ms 47436 KB Output is correct
6 Correct 698 ms 47360 KB Output is correct
7 Correct 800 ms 47436 KB Output is correct
8 Correct 778 ms 47360 KB Output is correct
9 Correct 592 ms 47696 KB Output is correct
10 Correct 694 ms 47184 KB Output is correct
11 Correct 803 ms 47184 KB Output is correct
12 Correct 7 ms 33112 KB Output is correct
13 Runtime error 273 ms 96200 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -