oj.uz

Submission #993775

# Submission time Handle Problem Language Result Execution time Memory
993775 2024-06-06T12:08:12 Z Valaki2 Factories (JOI14_factories) C++14
100 / 100
 3542 ms 264640 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 5e5;
const ll inf = 1e16 + 42;

struct edge {
    int to;
    ll wei;
    int subtree_size;
    edge() : to(0), wei(0ll), subtree_size(0) {}
    edge(int to_, ll wei_, int subtree_size_) :
        to(to_), wei(wei_), subtree_size(subtree_size_) {}
};

const int logn = 20;

int n;
vector<edge > graph[1 + maxn];
bool done[1 + maxn];
vector<int> ctree[1 + maxn];
int cpar[1 + maxn];
int croot;
int dep[1 + maxn];
int lift[1 + maxn][logn];
ll pref[1 + maxn];
ll centdist[1 + maxn][logn];
int level[1 + maxn];

int dfs_subtree(int cur, int par, const int &all_size) {
    int cur_size = 1;
    for(edge &nei : graph[cur]) {
        if(nei.to != par && !done[nei.to]) {
            int this_size = dfs_subtree(nei.to, cur, all_size);
            nei.subtree_size = this_size;
            cur_size += this_size;
        }
    }
    for(edge &nei : graph[cur]) {
        if(nei.to == par) {
            nei.subtree_size = all_size - cur_size;
            break;
        }
    }
    return cur_size;
}

void dfs_dist(int cur, int par, ll cur_dist, const int &cur_level) {
    centdist[cur][cur_level] = cur_dist;
    for(edge nei : graph[cur]) {
        if(nei.to != par && !done[nei.to]) {
            dfs_dist(nei.to, cur, cur_dist + nei.wei, cur_level);
        }
    }
}

void decompose(int cur, int prev_centroid, int all_size) {
    dfs_subtree(cur, -1, all_size);
    while(true) {
        pii best = mp(-1, all_size / 2);
        for(edge nei : graph[cur]) {
            if(!done[nei.to]) {
                pii cur_pair = mp(nei.to, nei.subtree_size);
                if(cur_pair.se > best.se) {
                    best = cur_pair;
                }
            }
        }
        /*cout << cur << " " << prev_centroid << " " << all_size << endl;
        for(edge e : graph[1]) {
            cout << e.to << " " << e.subtree_size << endl;
        }*/
        if(best.fi == -1) {
            break;
        }
        cur = best.fi;
    }
    // centroid: cur
    cpar[cur] = prev_centroid;
    if(prev_centroid != -1) {
        ctree[prev_centroid].pb(cur);
        level[cur] = level[cpar[cur]] + 1;
    } else {
        croot = cur;
    }
    dfs_dist(cur, -1, 0, level[cur]);
    done[cur] = true;
    for(edge nei : graph[cur]) {
        if(!done[nei.to]) {
            decompose(nei.to, cur, nei.subtree_size);
        }
    }
}

void dfs_depth(int cur) {
    for(edge nei : graph[cur]) {
        if(nei.to != lift[cur][0]) {
            lift[nei.to][0] = cur;
            dep[nei.to] = dep[cur] + 1;
            pref[nei.to] = pref[cur] + nei.wei;
            dfs_depth(nei.to);
        }
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) {
        swap(a, b);
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(dep[b] - (1 << j) >= dep[a]) {
            b = lift[b][j];
        }
    }
    if(a == b) {
        return a;
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(lift[a][j] != lift[b][j]) {
            a = lift[a][j];
            b = lift[b][j];
        }
    }
    return lift[b][0];
}

ll dist(int a, int b) {
    int c = lca(a, b);
    return pref[a] + pref[b] - 2 * pref[c];
}

ll nearest[1 + maxn];
bool to_reset[1 + maxn];
vector<int> reset;

void Init(signed N, signed A[], signed B[], signed D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++) {
        int a = A[i], b = B[i], d = D[i];
        a++;
        b++;
        graph[a].pb(edge(b, d, 0));
        graph[b].pb(edge(a, d, 0));
    }
    /*for(int i = 1; i <= n; i++) {
        cout << i << endl;
        for(edge e : graph[i]) {
            cout << e.to << " " << e.wei << endl;
        }
    }
    return;*/
    decompose(1, -1, n);
    lift[1][0] = 1;
    dfs_depth(1);
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        nearest[i] = inf;
    }
    /*for(int i = 1; i <= n; i++) {
        cout << cpar[i] << " ";
    }
    cout << endl;*/
}

void upd(int cur) {
    int centroid = cur;
    while(centroid != -1) {
        if(!to_reset[centroid]) {
            to_reset[centroid] = true;
            reset.pb(centroid);
        }
        nearest[centroid] = min(nearest[centroid], centdist[cur][level[centroid]]);
        centroid = cpar[centroid];
    }
}

ll query(int cur) {
    int centroid = cur;
    ll res = inf;
    while(centroid != -1) {
        res = min(res, centdist[cur][level[centroid]] + nearest[centroid]);
        centroid = cpar[centroid];
    }
    return res;
}

ll Query(signed S, signed X[], signed T, signed Y[]) {
    vector<int> a, b;
    for(int i = 0; i < S; i++) {
        a.pb(X[i] + 1);
    }
    for(int j = 0; j < T; j++) {
        b.pb(Y[j] + 1);
    }
    for(int y : b) {
        upd(y);
    }
    ll ans = inf;
    for(int x : a) {
        ans = min(ans, query(x));
    }
    for(int r : reset) {
        to_reset[r] = false;
        nearest[r] = inf;
    }
    reset.clear();
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24412 KB Output is correct
2 Correct 215 ms 42324 KB Output is correct
3 Correct 252 ms 42324 KB Output is correct
4 Correct 259 ms 43088 KB Output is correct
5 Correct 272 ms 43344 KB Output is correct
6 Correct 164 ms 43056 KB Output is correct
7 Correct 247 ms 43108 KB Output is correct
8 Correct 253 ms 43092 KB Output is correct
9 Correct 274 ms 43684 KB Output is correct
10 Correct 181 ms 42948 KB Output is correct
11 Correct 277 ms 43088 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Correct 1586 ms 225580 KB Output is correct
3 Correct 2420 ms 227736 KB Output is correct
4 Correct 576 ms 216556 KB Output is correct
5 Correct 3367 ms 258420 KB Output is correct
6 Correct 2703 ms 231804 KB Output is correct
7 Correct 740 ms 83280 KB Output is correct
8 Correct 306 ms 82176 KB Output is correct
9 Correct 919 ms 88400 KB Output is correct
10 Correct 771 ms 84820 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24412 KB Output is correct
2 Correct 215 ms 42324 KB Output is correct
3 Correct 252 ms 42324 KB Output is correct
4 Correct 259 ms 43088 KB Output is correct
5 Correct 272 ms 43344 KB Output is correct
6 Correct 164 ms 43056 KB Output is correct
7 Correct 247 ms 43108 KB Output is correct
8 Correct 253 ms 43092 KB Output is correct
9 Correct 274 ms 43684 KB Output is correct
10 Correct 181 ms 42948 KB Output is correct
11 Correct 277 ms 43088 KB Output is correct
12 Correct 11 ms 24152 KB Output is correct
13 Correct 1586 ms 225580 KB Output is correct
14 Correct 2420 ms 227736 KB Output is correct
15 Correct 576 ms 216556 KB Output is correct
16 Correct 3367 ms 258420 KB Output is correct
17 Correct 2703 ms 231804 KB Output is correct
18 Correct 740 ms 83280 KB Output is correct
19 Correct 306 ms 82176 KB Output is correct
20 Correct 919 ms 88400 KB Output is correct
21 Correct 771 ms 84820 KB Output is correct
22 Correct 1729 ms 235072 KB Output is correct
23 Correct 1906 ms 237300 KB Output is correct
24 Correct 2762 ms 238824 KB Output is correct
25 Correct 2834 ms 242452 KB Output is correct
26 Correct 2789 ms 238068 KB Output is correct
27 Correct 3542 ms 264640 KB Output is correct
28 Correct 661 ms 228576 KB Output is correct
29 Correct 3073 ms 237336 KB Output is correct
30 Correct 3139 ms 236556 KB Output is correct
31 Correct 2933 ms 237356 KB Output is correct
32 Correct 903 ms 89972 KB Output is correct
33 Correct 300 ms 83032 KB Output is correct
34 Correct 542 ms 80916 KB Output is correct
35 Correct 553 ms 80976 KB Output is correct
36 Correct 742 ms 81176 KB Output is correct
37 Correct 714 ms 81624 KB Output is correct