oj.uz

Submission #964775

# Submission time Handle Problem Language Result Execution time Memory
964775 2024-04-17T14:11:00 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4841 ms 340748 KB 
#include <bits/stdc++.h>
 
#ifdef DEBUG
    #include <debug.hpp>
#else
    #define debug(...) 42
#endif
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
const ll INF = 1e18;
 
vector<vector<pair<int, ll>>> gr;
vector<int> sz, used, act;
vector<ll> cls;
vector<vector<int>> cent;
vector<vector<ll>> dist;
int now = 0;
 
int find_sz(int v, int p) {
    sz[v] = 1;
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        sz[v] += find_sz(to, v);
    }
    return sz[v];
}
 
int centr(int v, int p, int cn) {
    bool flag = 1;
    while (flag) {
        flag = 0;
        for (auto [to, w] : gr[v]) {
            if (used[to] || to == p) continue;
            if (sz[to] > cn / 2) {
                p = v;
                v = to;
                flag = 1;
                break;
            }
        }
    }
    return v;
}
 
void dfs(int v, int c, int p = -1, ll d = 0) {
    cent[v].push_back(c);
    dist[v].push_back(d);
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        dfs(to, c, v, d + w);
    }
} 
 
void Decomp(int v) {
    int cn = find_sz(v, v);
    int c = centr(v, v, cn); 
    used[c] = 1;
    dfs(c, c);
    for (auto [to, w] : gr[c]) {
        if (used[to]) continue;
        Decomp(to);
    }
}
 
void Init(int N, int A[], int B[], int D[]) {
    gr.assign(N, {}); 
    used.assign(N, 0);
    sz.assign(N, 0);
    cent.assign(N, {});
    dist.assign(N, {});
    cls.assign(N, INF);
    act.assign(N, 0);
    
    for (int i = 0; i < N - 1; ++i) {
        gr[A[i]].emplace_back(B[i], D[i]);
        gr[B[i]].emplace_back(A[i], D[i]);
    }
 
    Decomp(0);
}
 
void Update(int v) {
    for (size_t j = 0; j < cent[v].size(); ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            cls[c] = min(cls[c], dist[v][j]);
        } else {
            cls[c] = dist[v][j]; 
            act[c] = now;
        }
    }
}
 
ll GetMin(int v) {
    ll res = INF;
    for (size_t j = 0; j < cent[v].size(); ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            res = min(res, dist[v][j] + cls[c]);
        }
    }
    return res;
}
 
ll Query(int S, int X[], int T, int Y[]) {
    // go through all X[i] centroids and update cls  
    for (int i = 0; i < S; ++i) {
        Update(X[i]);
    }
 
    // go through all Y[i] centroids and update min(res, dist[Y[i]][c] + cls[c])
    ll res = INF;
    for (int i = 0; i < T; ++i) {
        res = min(res, GetMin(Y[i])); 
    }
 
    // Update actuality
    ++now;
 
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17244 KB Output is correct
2 Correct 248 ms 31924 KB Output is correct
3 Correct 245 ms 32460 KB Output is correct
4 Correct 255 ms 28608 KB Output is correct
5 Correct 261 ms 28496 KB Output is correct
6 Correct 159 ms 29216 KB Output is correct
7 Correct 247 ms 32208 KB Output is correct
8 Correct 305 ms 32028 KB Output is correct
9 Correct 256 ms 32436 KB Output is correct
10 Correct 178 ms 31416 KB Output is correct
11 Correct 240 ms 32076 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2621 ms 214736 KB Output is correct
3 Correct 4133 ms 271312 KB Output is correct
4 Correct 900 ms 141656 KB Output is correct
5 Correct 4510 ms 340748 KB Output is correct
6 Correct 3741 ms 271988 KB Output is correct
7 Correct 936 ms 72616 KB Output is correct
8 Correct 321 ms 55748 KB Output is correct
9 Correct 1047 ms 83072 KB Output is correct
10 Correct 845 ms 73388 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17244 KB Output is correct
2 Correct 248 ms 31924 KB Output is correct
3 Correct 245 ms 32460 KB Output is correct
4 Correct 255 ms 28608 KB Output is correct
5 Correct 261 ms 28496 KB Output is correct
6 Correct 159 ms 29216 KB Output is correct
7 Correct 247 ms 32208 KB Output is correct
8 Correct 305 ms 32028 KB Output is correct
9 Correct 256 ms 32436 KB Output is correct
10 Correct 178 ms 31416 KB Output is correct
11 Correct 240 ms 32076 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 2621 ms 214736 KB Output is correct
14 Correct 4133 ms 271312 KB Output is correct
15 Correct 900 ms 141656 KB Output is correct
16 Correct 4510 ms 340748 KB Output is correct
17 Correct 3741 ms 271988 KB Output is correct
18 Correct 936 ms 72616 KB Output is correct
19 Correct 321 ms 55748 KB Output is correct
20 Correct 1047 ms 83072 KB Output is correct
21 Correct 845 ms 73388 KB Output is correct
22 Correct 2949 ms 219264 KB Output is correct
23 Correct 3038 ms 222332 KB Output is correct
24 Correct 4412 ms 275276 KB Output is correct
25 Correct 4280 ms 278292 KB Output is correct
26 Correct 4250 ms 276460 KB Output is correct
27 Correct 4841 ms 339724 KB Output is correct
28 Correct 1077 ms 148100 KB Output is correct
29 Correct 4099 ms 275888 KB Output is correct
30 Correct 4179 ms 275108 KB Output is correct
31 Correct 4222 ms 276036 KB Output is correct
32 Correct 1055 ms 83664 KB Output is correct
33 Correct 317 ms 56004 KB Output is correct
34 Correct 656 ms 67044 KB Output is correct
35 Correct 668 ms 67820 KB Output is correct
36 Correct 813 ms 71592 KB Output is correct
37 Correct 784 ms 71660 KB Output is correct