oj.uz

Submission #843501

# Submission time Handle Problem Language Result Execution time Memory
843501 2023-09-04T03:47:13 Z bachhoangxuan Factories (JOI14_factories) C++17
100 / 100
 2315 ms 448068 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<ll, ll>
#define vi vector<ll>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (ll)x.size()
using namespace std;

const ll mxN = 5e5 + 5;
const ll oo = 1e18;

ll n;
vector<vii> G;

vi vtn;
vector<vii> vt;

ll dis[mxN];
pii sparse[20][2 * mxN];
ll timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];

void dfs(ll v, ll 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() {
    for(ll p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(ll j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}

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

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

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    G.resize(n); vt.resize(n);
    for(ll 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(ll i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(ll i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }

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

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

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

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

    stack<ll> s;
    for(ll 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, ll v, ll 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(ll 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 u:vtn){
        cur[u]=0;
        vt[u].clear();
    }
    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 557 ms 59016 KB Output is correct
3 Correct 552 ms 58812 KB Output is correct
4 Correct 556 ms 59144 KB Output is correct
5 Correct 512 ms 59216 KB Output is correct
6 Correct 341 ms 58960 KB Output is correct
7 Correct 542 ms 58968 KB Output is correct
8 Correct 548 ms 59216 KB Output is correct
9 Correct 512 ms 59216 KB Output is correct
10 Correct 340 ms 58960 KB Output is correct
11 Correct 550 ms 58808 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43608 KB Output is correct
2 Correct 910 ms 415232 KB Output is correct
3 Correct 939 ms 419844 KB Output is correct
4 Correct 703 ms 413020 KB Output is correct
5 Correct 931 ms 447916 KB Output is correct
6 Correct 991 ms 420528 KB Output is correct
7 Correct 735 ms 141284 KB Output is correct
8 Correct 489 ms 139796 KB Output is correct
9 Correct 571 ms 145468 KB Output is correct
10 Correct 783 ms 140100 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 557 ms 59016 KB Output is correct
3 Correct 552 ms 58812 KB Output is correct
4 Correct 556 ms 59144 KB Output is correct
5 Correct 512 ms 59216 KB Output is correct
6 Correct 341 ms 58960 KB Output is correct
7 Correct 542 ms 58968 KB Output is correct
8 Correct 548 ms 59216 KB Output is correct
9 Correct 512 ms 59216 KB Output is correct
10 Correct 340 ms 58960 KB Output is correct
11 Correct 550 ms 58808 KB Output is correct
12 Correct 6 ms 43608 KB Output is correct
13 Correct 910 ms 415232 KB Output is correct
14 Correct 939 ms 419844 KB Output is correct
15 Correct 703 ms 413020 KB Output is correct
16 Correct 931 ms 447916 KB Output is correct
17 Correct 991 ms 420528 KB Output is correct
18 Correct 735 ms 141284 KB Output is correct
19 Correct 489 ms 139796 KB Output is correct
20 Correct 571 ms 145468 KB Output is correct
21 Correct 783 ms 140100 KB Output is correct
22 Correct 2045 ms 424784 KB Output is correct
23 Correct 1646 ms 423616 KB Output is correct
24 Correct 2315 ms 428460 KB Output is correct
25 Correct 2099 ms 429948 KB Output is correct
26 Correct 1664 ms 422480 KB Output is correct
27 Correct 2047 ms 448068 KB Output is correct
28 Correct 1353 ms 417968 KB Output is correct
29 Correct 1583 ms 421220 KB Output is correct
30 Correct 1546 ms 420508 KB Output is correct
31 Correct 1603 ms 420984 KB Output is correct
32 Correct 996 ms 151468 KB Output is correct
33 Correct 596 ms 144832 KB Output is correct
34 Correct 900 ms 141220 KB Output is correct
35 Correct 897 ms 141216 KB Output is correct
36 Correct 968 ms 141632 KB Output is correct
37 Correct 928 ms 141652 KB Output is correct