oj.uz

Submission #631754

# Submission time Handle Problem Language Result Execution time Memory
631754 2022-08-18T16:33:47 Z elkernos Factories (JOI14_factories) C++17
100 / 100
 2353 ms 143188 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpi;

namespace kactl {
template <class T>
struct RMQ {
    vector<vector<T>> jmp;
    void init(const vector<T> &V)
    {
        jmp.resize(1, vector<T>(V));
        for(int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j, 0, sz(jmp[k]))
                jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
        }
    }
    T query(int a, int b)
    {
        assert(a < b); // or return inf if a == b
        int dep = 31 - __builtin_clz(b - a);
        return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};
struct LCA {
    int T = 0;
    vi time, path, ret;
    vl depth;
    RMQ<int> rmq;
    void init(vector<vpi> &C)
    {
        time.resize(sz(C));
        depth.resize(sz(C));
        dfs(C, 0, -1);
        rmq.init(ret);
    }
    void dfs(vector<vpi> &C, int v, int par)
    {
        time[v] = T++;
        for(auto [y, d] : C[v]) {
            if(y != par) {
                path.push_back(v), ret.push_back(time[v]);
                depth[y] = depth[v] + d;
                dfs(C, y, v);
            }
        }
    }
    int lca(int a, int b)
    {
        if(a == b) return a;
        tie(a, b) = minmax(time[a], time[b]);
        return path[rmq.query(a, b)];
    }
    ll dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
};
vpi compressTree(LCA &lca, const vi &subset)
{
    vi li = subset, &T = lca.time;
    auto cmp = [&](int a, int b) { return T[a] < T[b]; };
    sort(all(li), cmp);
    int m = sz(li) - 1;
    rep(i, 0, m)
    {
        int a = li[i], b = li[i + 1];
        li.push_back(lca.lca(a, b));
    }
    sort(all(li), cmp);
    li.erase(unique(all(li)), li.end());
    vpi ret = {pii(li[0], li[0])};
    rep(i, 0, sz(li) - 1)
    {
        int a = li[i], b = li[i + 1];
        ret.emplace_back(lca.lca(a, b), b);
    }
    return ret;
}
}; // namespace kactl

using namespace kactl;
const int nax = 500123;

ll toX[nax], toY[nax];
vi ch[nax];

#define x first
#define y second

LCA lca;

void Init(int N, int A[], int B[], int D[])
{
    vector<vpi> g(N);
    for(int i = 0; i < N; i++) {
        toX[i] = toY[i] = 1e18;
    }
    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]);
    }
    lca.init(g);
}

ll ans;

void chmin(ll &a, ll b)
{
    if(a > b) {
        a = b;
    }
}

void dfs(int u)
{
    for(auto to : ch[u]) {
        dfs(to);
        chmin(toX[u], toX[to] + lca.dist(u, to));
        chmin(toY[u], toY[to] + lca.dist(u, to));
    }
    ans = min(ans, toX[u] + toY[u]);
}

ll Query(int S, int X[], int T, int Y[])
{
    vi s;
    for(int i = 0; i < S; i++) {
        toX[X[i]] = 0;
        s.emplace_back(X[i]);
    }
    for(int i = 0; i < T; i++) {
        toY[Y[i]] = 0;
        s.emplace_back(Y[i]);
    }
    vpi r = compressTree(lca, s);
    for(int i = 1; i < sz(r); i++) {
        ch[r[i].x].emplace_back(r[i].y);
    }
    ans = 1e18;
    dfs(r[0].x);
    for(auto [_, i] : r) {
        toX[i] = toY[i] = 1e18;
        ch[i].clear();
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12628 KB Output is correct
2 Correct 686 ms 30224 KB Output is correct
3 Correct 664 ms 30264 KB Output is correct
4 Correct 707 ms 30308 KB Output is correct
5 Correct 629 ms 30560 KB Output is correct
6 Correct 415 ms 30260 KB Output is correct
7 Correct 686 ms 30272 KB Output is correct
8 Correct 645 ms 30392 KB Output is correct
9 Correct 661 ms 30512 KB Output is correct
10 Correct 420 ms 30236 KB Output is correct
11 Correct 662 ms 30384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 1160 ms 124268 KB Output is correct
3 Correct 1216 ms 107468 KB Output is correct
4 Correct 806 ms 108108 KB Output is correct
5 Correct 1177 ms 136324 KB Output is correct
6 Correct 1365 ms 126080 KB Output is correct
7 Correct 1083 ms 48536 KB Output is correct
8 Correct 635 ms 48960 KB Output is correct
9 Correct 910 ms 49804 KB Output is correct
10 Correct 1012 ms 48760 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12628 KB Output is correct
2 Correct 686 ms 30224 KB Output is correct
3 Correct 664 ms 30264 KB Output is correct
4 Correct 707 ms 30308 KB Output is correct
5 Correct 629 ms 30560 KB Output is correct
6 Correct 415 ms 30260 KB Output is correct
7 Correct 686 ms 30272 KB Output is correct
8 Correct 645 ms 30392 KB Output is correct
9 Correct 661 ms 30512 KB Output is correct
10 Correct 420 ms 30236 KB Output is correct
11 Correct 662 ms 30384 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 1160 ms 124268 KB Output is correct
14 Correct 1216 ms 107468 KB Output is correct
15 Correct 806 ms 108108 KB Output is correct
16 Correct 1177 ms 136324 KB Output is correct
17 Correct 1365 ms 126080 KB Output is correct
18 Correct 1083 ms 48536 KB Output is correct
19 Correct 635 ms 48960 KB Output is correct
20 Correct 910 ms 49804 KB Output is correct
21 Correct 1012 ms 48760 KB Output is correct
22 Correct 2235 ms 111948 KB Output is correct
23 Correct 1923 ms 112720 KB Output is correct
24 Correct 2342 ms 112864 KB Output is correct
25 Correct 2353 ms 135640 KB Output is correct
26 Correct 2100 ms 134456 KB Output is correct
27 Correct 2252 ms 143188 KB Output is correct
28 Correct 1187 ms 135716 KB Output is correct
29 Correct 2041 ms 134348 KB Output is correct
30 Correct 2233 ms 134064 KB Output is correct
31 Correct 2080 ms 134204 KB Output is correct
32 Correct 1189 ms 60228 KB Output is correct
33 Correct 649 ms 52048 KB Output is correct
34 Correct 1132 ms 50360 KB Output is correct
35 Correct 1090 ms 50384 KB Output is correct
36 Correct 1188 ms 50616 KB Output is correct
37 Correct 1221 ms 50572 KB Output is correct