oj.uz

Submission #558629

# Submission time Handle Problem Language Result Execution time Memory
558629 2022-05-07T16:39:52 Z ddy888 Factories (JOI14_factories) C++17
100 / 100
 6267 ms 205156 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;

#include "factories.h"

const int MAXN = 500010, LOG = 20;
const ll INF = 1e18;
int n;
vector<pi> g[MAXN];

int tk[MAXN][LOG];
int dep[MAXN];
ll wd[MAXN];
int vis[MAXN];
ll close[MAXN];
ll dst[MAXN][LOG];

void dfs(int x, int pa) {
    dep[x] = dep[pa] + 1;
    vis[x] = 1;
    tk[x][0] = pa;
    for (int i = 1; i < LOG; ++i) {
        if (tk[x][i - 1] == -1) 
            continue;
        tk[x][i] = tk[tk[x][i - 1]][i - 1];
    }
    for (auto i: g[x]) {
        if (i.fi == pa || vis[i.fi])
            continue;
        wd[i.fi] = wd[x] + i.si;
        dfs(i.fi, x);
    }
}

int jump(int x, int d) {
    for (int i = 0; i < LOG; ++i) {
        if (x == -1)
            return -1;
        if (d & (1 << i))
            x = tk[x][i];
    }
    return x;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) // wlog x is further from root
        swap(x, y);
    x = jump(x, dep[x] - dep[y]);
    if (x == y)
        return x;
    for (int i = LOG - 1; i >= 0; --i) {
        int nx = tk[x][i], ny = tk[y][i];
        if (nx == -1 || ny == -1)
            continue;
        if (nx != ny) 
            x = nx, y = ny;
    }
    return tk[x][0];
}

ll dist(int x, int y) {
    return wd[x] + wd[y] - 2 * wd[lca(x, y)];
}

struct CentroidDecomposition {
    vector<int> sub;
    vector<int> rem;
    vector<int> tree;
    vector<int> lvl;

    void init(int nodes) {
        sub.resize(nodes + 1);
        rem.resize(nodes + 1);
        lvl.resize(nodes + 1);
        tree.resize(nodes + 1, -1);
        build(0, -1, 0);
    }

    int dfs(int u, int p) {
        sub[u] = 1;
        for (auto i: g[u]) {
            if (i.fi == p || rem[i.fi])
                continue;
            sub[u] += dfs(i.fi, u);
        }
        return sub[u];
    }

    int cent(int u, int sz, int p) {
        for (auto i: g[u]) {
            if (i.fi == p || rem[i.fi])
                continue;
            if (sub[i.fi] * 2 <= sz)
                continue;
            return cent(i.fi, sz, u);
        }
        return u;
    }

    void build(int u, int p, int l) {
        int c = cent(u, dfs(u, -1), -1);
        rem[c] = 1;
        tree[c] = p;    
        lvl[c] = l;
        for (auto i: g[c]) {
            if (rem[i.fi])
                continue;
            build(i.fi, c, l + 1);
        }
    }

    int par(int u) {
        return tree[u];
    }

    int level(int u) {
        return lvl[u];
    }
} cd;

void Init(int _N, int _A[], int _B[], int _D[]) {
    n = _N;
    for (int i = 0; i < n - 1; ++i) {
        int u = _A[i], v = _B[i], c = _D[i];
        // ++u, ++v;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    memset(tk, -1, sizeof tk);
    dfs(0, -1);
    cd.init(n + 1);
    for (int i = 0; i < n; ++i) {
        int v = i;
        for (int j = cd.lvl[i]; j >= 0; --j) {
            dst[i][j] = dist(i, v);
            v = cd.par(v);
        }   
    }
    for (int i = 0; i < n; ++i)
        close[i] = INF;
}

long long Query(int _S, int _X[], int _T, int _Y[]) {
    for (int i = 0; i < _S; ++i) {
        int node = _X[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            close[v] = min(close[v], dst[x][l]);
        }
    }
    ll ans = INF;
    for (int i = 0; i < _T; ++i) {
        int node = _Y[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            ans = min(ans, close[v] + dst[x][l]);
        }
    }
    for (int i = 0; i < _S; ++i) {
        int node = _X[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            close[v] = INF;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51716 KB Output is correct
2 Correct 285 ms 60508 KB Output is correct
3 Correct 329 ms 60520 KB Output is correct
4 Correct 307 ms 60504 KB Output is correct
5 Correct 376 ms 60748 KB Output is correct
6 Correct 249 ms 60604 KB Output is correct
7 Correct 315 ms 60524 KB Output is correct
8 Correct 323 ms 60560 KB Output is correct
9 Correct 349 ms 60808 KB Output is correct
10 Correct 235 ms 60684 KB Output is correct
11 Correct 384 ms 60544 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51404 KB Output is correct
2 Correct 2173 ms 180756 KB Output is correct
3 Correct 4539 ms 182492 KB Output is correct
4 Correct 752 ms 181504 KB Output is correct
5 Correct 5999 ms 205156 KB Output is correct
6 Correct 4291 ms 183544 KB Output is correct
7 Correct 926 ms 85716 KB Output is correct
8 Correct 381 ms 86340 KB Output is correct
9 Correct 1066 ms 89352 KB Output is correct
10 Correct 909 ms 86888 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51716 KB Output is correct
2 Correct 285 ms 60508 KB Output is correct
3 Correct 329 ms 60520 KB Output is correct
4 Correct 307 ms 60504 KB Output is correct
5 Correct 376 ms 60748 KB Output is correct
6 Correct 249 ms 60604 KB Output is correct
7 Correct 315 ms 60524 KB Output is correct
8 Correct 323 ms 60560 KB Output is correct
9 Correct 349 ms 60808 KB Output is correct
10 Correct 235 ms 60684 KB Output is correct
11 Correct 384 ms 60544 KB Output is correct
12 Correct 22 ms 51404 KB Output is correct
13 Correct 2173 ms 180756 KB Output is correct
14 Correct 4539 ms 182492 KB Output is correct
15 Correct 752 ms 181504 KB Output is correct
16 Correct 5999 ms 205156 KB Output is correct
17 Correct 4291 ms 183544 KB Output is correct
18 Correct 926 ms 85716 KB Output is correct
19 Correct 381 ms 86340 KB Output is correct
20 Correct 1066 ms 89352 KB Output is correct
21 Correct 909 ms 86888 KB Output is correct
22 Correct 2399 ms 182108 KB Output is correct
23 Correct 2484 ms 184416 KB Output is correct
24 Correct 4738 ms 184384 KB Output is correct
25 Correct 4605 ms 187408 KB Output is correct
26 Correct 4559 ms 184232 KB Output is correct
27 Correct 6267 ms 202964 KB Output is correct
28 Correct 836 ms 185172 KB Output is correct
29 Correct 4606 ms 183948 KB Output is correct
30 Correct 4702 ms 183264 KB Output is correct
31 Correct 4649 ms 183852 KB Output is correct
32 Correct 1100 ms 90184 KB Output is correct
33 Correct 385 ms 86848 KB Output is correct
34 Correct 631 ms 84008 KB Output is correct
35 Correct 658 ms 83956 KB Output is correct
36 Correct 916 ms 84428 KB Output is correct
37 Correct 958 ms 84452 KB Output is correct