oj.uz

Submission #843546

# Submission time Handle Problem Language Result Execution time Memory
843546 2023-09-04T04:39:03 Z daoquanglinh2007 Factories (JOI14_factories) C++17
100 / 100
 2001 ms 302172 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define vil vector <pair <int, ll> >
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 1e6 + 5;
const ll oo = 1e18;

int n;
vector<vil> G;

vi vtn;
vector<vil> vt;

ll dis[mxN];
pii sparse[25][mxN];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];

void dfs(int v, int p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    sparse[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;

    for(auto &[u, w] : G[v]) {
        if(u == p) continue;
        dis[u] = dis[v] + w;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }

    tout[v] = ++timer;
}

void build_sparse() {
    assert(ecnt <= 2*n);
    for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int LCA(int u, int v) {
    int l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    int len = r - l + 1, lg_len = __lg(len), res = min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    G.resize(n); vt.resize(n);
    for(int i = 0; i < N - 1; ++i) {
        G[A[i]].emplace_back(B[i], D[i]);
        G[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0); build_sparse();
}

long long Query(int S, int X[], int T, int Y[]) {
    queue<pii> q;

    for(int i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }

    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });

    for(int i = 0; i < S + T - 1; ++i) {
        vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
    }

    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());

    auto add_vt = [&](int u, int v, ll w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };

    stack<int> s;
    while (!s.empty()) s.pop();
    for(int i = 0; i < isz(vtn); ++i) {
        while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop();
        if(s.empty()) s.emplace(vtn[i]);
        else {
            add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
            s.emplace(vtn[i]);
        }
    }

    ll res = oo;

    auto dfs = [&](auto self, int v, int p) -> vll {
        vll cur_dis(2, oo);
        if(cur[v]) cur_dis[cur[v] - 1] = 0;
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            vll tmp = self(self, u, v);
            for(int i = 0; i < 2; ++i)
                cur_dis[i] = min(cur_dis[i], tmp[i] + w);
        }
        res = min(res, accumulate(all(cur_dis), 0LL));
        return cur_dis;
    };

    dfs(dfs, vtn[0], 0);

    for (int i = 0; i < isz(vtn); i++){
        vt[vtn[i]].clear();
        cur[vtn[i]] = 0;
    }
    vtn.clear();

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 553 ms 58964 KB Output is correct
3 Correct 553 ms 59104 KB Output is correct
4 Correct 582 ms 58960 KB Output is correct
5 Correct 523 ms 59484 KB Output is correct
6 Correct 348 ms 58708 KB Output is correct
7 Correct 547 ms 58960 KB Output is correct
8 Correct 549 ms 58712 KB Output is correct
9 Correct 526 ms 59080 KB Output is correct
10 Correct 359 ms 58964 KB Output is correct
11 Correct 542 ms 58708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43612 KB Output is correct
2 Correct 877 ms 262872 KB Output is correct
3 Correct 881 ms 268360 KB Output is correct
4 Correct 641 ms 259084 KB Output is correct
5 Correct 877 ms 302172 KB Output is correct
6 Correct 937 ms 269008 KB Output is correct
7 Correct 663 ms 113944 KB Output is correct
8 Correct 490 ms 112376 KB Output is correct
9 Correct 531 ms 118620 KB Output is correct
10 Correct 654 ms 114256 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 553 ms 58964 KB Output is correct
3 Correct 553 ms 59104 KB Output is correct
4 Correct 582 ms 58960 KB Output is correct
5 Correct 523 ms 59484 KB Output is correct
6 Correct 348 ms 58708 KB Output is correct
7 Correct 547 ms 58960 KB Output is correct
8 Correct 549 ms 58712 KB Output is correct
9 Correct 526 ms 59080 KB Output is correct
10 Correct 359 ms 58964 KB Output is correct
11 Correct 542 ms 58708 KB Output is correct
12 Correct 6 ms 43612 KB Output is correct
13 Correct 877 ms 262872 KB Output is correct
14 Correct 881 ms 268360 KB Output is correct
15 Correct 641 ms 259084 KB Output is correct
16 Correct 877 ms 302172 KB Output is correct
17 Correct 937 ms 269008 KB Output is correct
18 Correct 663 ms 113944 KB Output is correct
19 Correct 490 ms 112376 KB Output is correct
20 Correct 531 ms 118620 KB Output is correct
21 Correct 654 ms 114256 KB Output is correct
22 Correct 1911 ms 271872 KB Output is correct
23 Correct 1670 ms 270808 KB Output is correct
24 Correct 2001 ms 275912 KB Output is correct
25 Correct 1894 ms 277580 KB Output is correct
26 Correct 1539 ms 270928 KB Output is correct
27 Correct 1938 ms 299968 KB Output is correct
28 Correct 1218 ms 264516 KB Output is correct
29 Correct 1480 ms 269488 KB Output is correct
30 Correct 1498 ms 268856 KB Output is correct
31 Correct 1440 ms 269388 KB Output is correct
32 Correct 864 ms 122336 KB Output is correct
33 Correct 522 ms 115744 KB Output is correct
34 Correct 861 ms 113608 KB Output is correct
35 Correct 801 ms 113744 KB Output is correct
36 Correct 877 ms 114516 KB Output is correct
37 Correct 852 ms 114512 KB Output is correct