oj.uz

답안 #856050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856050 2023-10-02T15:56:13 Z overwatch9 공장들 (JOI14_factories) C++17
0 / 100
 14 ms 25432 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "factories.h"
using namespace std;
using ll = long long;
const int maxn = 10 + 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 25344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 25432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 25344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -