oj.uz

Submission #856049

# Submission time Handle Problem Language Result Execution time Memory
856049 2023-10-02T15:53:56 Z overwatch9 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 173784 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "factories.h"
using namespace std;
using ll = long long;
const int maxn = 5e5 + 1;
vector <pair <int, int>> adj[maxn];
int anc[maxn][20];
bool blocked[maxn];
int sz[maxn], visit[maxn], finish[maxn];
ll depth[maxn];
vector <int> centroids[maxn];
ll dis[maxn];
int get_subtree_sz(int s, int p) {
    sz[s] = 1;
    for (auto i : adj[s]) {
        if (blocked[i.first] || i.first == p)
            continue;
        sz[s] += get_subtree_sz(i.first, s);
    }
    return sz[s];
}
int get_centroid(int s, int p, int st_sz) {
    for (auto i : adj[s]) {
        if (i.first == p || blocked[i.first])
            continue;
        if (sz[i.first] * 2 > st_sz)
            return get_centroid(i.first, s, st_sz);
    }
    return s;
}
void add_centroid(int s, int p, int centroid) {
    centroids[s].push_back(centroid);
    for (auto i : adj[s]) {
        if (i.first == p || blocked[i.first])
            continue;
        add_centroid(i.first, s, centroid);
    }
}
void dfs(int s) {
    int centroid = get_centroid(s, s, get_subtree_sz(s, s));
    blocked[centroid] = true;
    add_centroid(centroid, centroid, centroid);
    for (auto i : adj[centroid]) {
        if (blocked[i.first])
            continue;
        dfs(i.first);
    }
}
int t = 0;
void dfs2(int s, int p) {
    anc[s][0] = p;
    visit[s] = t++;
    for (int i = 1; i < 20; i++)
        anc[s][i] = anc[anc[s][i-1]][i-1];
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        depth[i.first] = depth[s] + i.second;
        dfs2(i.first, s);
    }
    finish[s] = t++;
}
bool is_ancestor(int a, int b) {
    return visit[a] <= visit[b] && finish[a] >= finish[b];
}
int get_lca(int a, int b) {
    if (is_ancestor(a, b))
        return a;
    if (is_ancestor(b, a))
        return b;
    int lca = a;
    for (int i = 19; i >= 0; i--) {
        if (!is_ancestor(anc[lca][i], b))
            lca = anc[lca][i];
    }
    return anc[lca][0];
}
void update_dis(int s) {
    for (auto centroid : centroids[s]) {
        int lca = get_lca(centroid, s);
        dis[centroid] = min(dis[centroid], depth[centroid] + depth[s] - 2 * depth[lca]);
    }
}
ll get_ans(int s) {
    ll ans = 1e16;
    for (auto centroid : centroids[s]) {
        int lca = get_lca(centroid, s);
        ans = min(ans, dis[centroid] + depth[centroid] + depth[s] - 2 * depth[lca]);
    }
    return ans;
}
void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        A[i]++;
        B[i]++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(1);
    dfs2(1, 1);
}
ll Query(int S, int X[], int T, int Y[]) {
    fill(dis, dis + maxn, 1e16);
    for (int i = 0; i < S; i++) {
        update_dis(X[i]+1);
    }
    ll ans = 1e16;
    for (int i = 0; i < T; i++) {
        ll tp = get_ans(Y[i] + 1);
        ans = min(ans, tp);
    }
    return ans;
}
// int main() {
//     int N, q;
//     cin >> N >> q;
//     int A[maxn], B[maxn], D[maxn];
//     for (int i = 0; i < N-1; i++)
//         cin >> A[i] >> B[i] >> D[i];
//     Init(N, A, B, D);
//     while (q--) {
//         int S, T;
//         cin >> S >> T;
//         int X[maxn], Y[maxn];
//         for (int i = 0; i < S; i++)
//             cin >> X[i];
//         for (int i = 0; i < T; i++)
//             cin >> Y[i];
//         cout << Query(S, X, T, Y) << '\n';
//     }
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 54108 KB Output is correct
2 Correct 1241 ms 68356 KB Output is correct
3 Correct 1719 ms 68524 KB Output is correct
4 Correct 1687 ms 68508 KB Output is correct
5 Correct 1216 ms 68944 KB Output is correct
6 Correct 962 ms 68260 KB Output is correct
7 Correct 1728 ms 68436 KB Output is correct
8 Correct 1745 ms 68524 KB Output is correct
9 Correct 1219 ms 68980 KB Output is correct
10 Correct 954 ms 68084 KB Output is correct
11 Correct 1712 ms 68524 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 53852 KB Output is correct
2 Execution timed out 8037 ms 173784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 54108 KB Output is correct
2 Correct 1241 ms 68356 KB Output is correct
3 Correct 1719 ms 68524 KB Output is correct
4 Correct 1687 ms 68508 KB Output is correct
5 Correct 1216 ms 68944 KB Output is correct
6 Correct 962 ms 68260 KB Output is correct
7 Correct 1728 ms 68436 KB Output is correct
8 Correct 1745 ms 68524 KB Output is correct
9 Correct 1219 ms 68980 KB Output is correct
10 Correct 954 ms 68084 KB Output is correct
11 Correct 1712 ms 68524 KB Output is correct
12 Correct 93 ms 53852 KB Output is correct
13 Execution timed out 8037 ms 173784 KB Time limit exceeded
14 Halted 0 ms 0 KB -