oj.uz

Submission #856051

# Submission time Handle Problem Language Result Execution time Memory
856051 2023-10-02T15:56:30 Z overwatch9 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 155404 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];
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, vector <ll> &dis) {
    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, vector <ll> &dis) {
    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[]) {
    vector <ll> dis(maxn, 1e16);
    for (int i = 0; i < S; i++) {
        update_dis(X[i]+1, dis);
    }
    ll ans = 1e16;
    for (int i = 0; i < T; i++) {
        ll tp = get_ans(Y[i] + 1, dis);
        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 109 ms 54008 KB Output is correct
2 Correct 1261 ms 58964 KB Output is correct
3 Correct 1742 ms 58864 KB Output is correct
4 Correct 1721 ms 58868 KB Output is correct
5 Correct 1267 ms 59124 KB Output is correct
6 Correct 944 ms 58792 KB Output is correct
7 Correct 1710 ms 58972 KB Output is correct
8 Correct 1762 ms 58876 KB Output is correct
9 Correct 1311 ms 59132 KB Output is correct
10 Correct 945 ms 58616 KB Output is correct
11 Correct 1703 ms 58876 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 54008 KB Output is correct
2 Correct 1261 ms 58964 KB Output is correct
3 Correct 1742 ms 58864 KB Output is correct
4 Correct 1721 ms 58868 KB Output is correct
5 Correct 1267 ms 59124 KB Output is correct
6 Correct 944 ms 58792 KB Output is correct
7 Correct 1710 ms 58972 KB Output is correct
8 Correct 1762 ms 58876 KB Output is correct
9 Correct 1311 ms 59132 KB Output is correct
10 Correct 945 ms 58616 KB Output is correct
11 Correct 1703 ms 58876 KB Output is correct
12 Correct 90 ms 53852 KB Output is correct
13 Execution timed out 8086 ms 155404 KB Time limit exceeded
14 Halted 0 ms 0 KB -