oj.uz

Submission #843413

# Submission time Handle Problem Language Result Execution time Memory
843413 2023-09-04T01:46:25 Z TranGiaHuy1508 Factories (JOI14_factories) C++17
100 / 100
 2108 ms 305448 KB 
// Credit: CDuongg

#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 isz(x) (int)x.size()
using namespace std;

const int mxN = 5e5 + 5;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
vector<vector<pair<int, ll>>> vt;
 
ll dis[mxN];
pii sparse[21][2 * 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() {
    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);
    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(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;
    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 dfs1 = [&](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;
    };
 
    dfs1(dfs1, vtn[0], 0);
 
    for(int i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 0;
        vt[Y[i]].clear();
    }
    for (auto i: vtn) vt[i].clear();
    vtn.clear();
 
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 591 ms 56736 KB Output is correct
3 Correct 578 ms 56736 KB Output is correct
4 Correct 617 ms 56936 KB Output is correct
5 Correct 548 ms 57288 KB Output is correct
6 Correct 362 ms 56652 KB Output is correct
7 Correct 580 ms 56776 KB Output is correct
8 Correct 564 ms 56912 KB Output is correct
9 Correct 556 ms 57116 KB Output is correct
10 Correct 347 ms 56656 KB Output is correct
11 Correct 564 ms 56780 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43612 KB Output is correct
2 Correct 922 ms 246240 KB Output is correct
3 Correct 983 ms 250996 KB Output is correct
4 Correct 716 ms 265076 KB Output is correct
5 Correct 920 ms 301760 KB Output is correct
6 Correct 1040 ms 270196 KB Output is correct
7 Correct 707 ms 121820 KB Output is correct
8 Correct 509 ms 121132 KB Output is correct
9 Correct 554 ms 126404 KB Output is correct
10 Correct 735 ms 122504 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 591 ms 56736 KB Output is correct
3 Correct 578 ms 56736 KB Output is correct
4 Correct 617 ms 56936 KB Output is correct
5 Correct 548 ms 57288 KB Output is correct
6 Correct 362 ms 56652 KB Output is correct
7 Correct 580 ms 56776 KB Output is correct
8 Correct 564 ms 56912 KB Output is correct
9 Correct 556 ms 57116 KB Output is correct
10 Correct 347 ms 56656 KB Output is correct
11 Correct 564 ms 56780 KB Output is correct
12 Correct 7 ms 43612 KB Output is correct
13 Correct 922 ms 246240 KB Output is correct
14 Correct 983 ms 250996 KB Output is correct
15 Correct 716 ms 265076 KB Output is correct
16 Correct 920 ms 301760 KB Output is correct
17 Correct 1040 ms 270196 KB Output is correct
18 Correct 707 ms 121820 KB Output is correct
19 Correct 509 ms 121132 KB Output is correct
20 Correct 554 ms 126404 KB Output is correct
21 Correct 735 ms 122504 KB Output is correct
22 Correct 2009 ms 278808 KB Output is correct
23 Correct 1664 ms 279112 KB Output is correct
24 Correct 2108 ms 283160 KB Output is correct
25 Correct 1894 ms 285060 KB Output is correct
26 Correct 1652 ms 277892 KB Output is correct
27 Correct 1798 ms 305448 KB Output is correct
28 Correct 1280 ms 275704 KB Output is correct
29 Correct 1493 ms 276492 KB Output is correct
30 Correct 1581 ms 275896 KB Output is correct
31 Correct 1564 ms 276652 KB Output is correct
32 Correct 855 ms 130504 KB Output is correct
33 Correct 549 ms 123332 KB Output is correct
34 Correct 879 ms 121332 KB Output is correct
35 Correct 872 ms 121332 KB Output is correct
36 Correct 908 ms 121932 KB Output is correct
37 Correct 839 ms 122096 KB Output is correct