oj.uz

Submission #908195

# Submission time Handle Problem Language Result Execution time Memory
908195 2024-01-16T09:23:04 Z typ_ik Factories (JOI14_factories) C++17
100 / 100
 5644 ms 369212 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std; 

const int N = 5e5 + 128;
const ll INF = 1e15 + 128; 
vector < pair<int, int> > g[N];
int n, q;
bool was[N];
int h[N]; 
ll res[N];   

void dfs(int v, int p = -1) {
    h[v] = 1;    

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            dfs(to, v), h[v] += h[to];
}  

vector < pair<int, ll> > p[N];

void calc(int v, int cent, ll val, int pr = -1) {
    p[v].push_back(make_pair(cent, val));

    for (auto& [to, len] : g[v])
        if (to != pr && !was[to])
            calc(to, cent, val+len, v);
} 

int find_centroid(int v, int pr, int sz) { 
    for (auto& [to, len] : g[v])
        if (to != pr && h[to] > sz / 2 && !was[to])
            return find_centroid(to, v, sz);
    return v;
} 

void decompose(int v, int pr = -1) { 
    dfs(v); 

    int c = find_centroid(v, -1, h[v]);    

    calc(c, c, 0);
    was[c] = true;

    for (auto& [to, len] : g[c])
        if (!was[to])
            decompose(to, c);
}

void update(int v) {
    for (auto& [x, d] : p[v])
        res[x] = min(res[x], d); 
}

void reset(int v) {
    for (auto& [x, d] : p[v])
        res[x] = INF; 
}

ll get(int v) {
    ll ans = INF;
    for (auto& [x, d] : p[v])
        ans = min(ans, d + res[x]); 
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i + 1 < n; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    for (int i = 0; i <= n; i++)
        res[i] = INF;
    decompose(1); 
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i]);
    ll tot = INF;
    for (int i = 0; i < T; i++)
        tot = min(tot, get(Y[i]));
    for (int i = 0; i < S; i++)
        reset(X[i]);
    return tot;
}   

// main() {
//     boost;
//     int A[] = {0, 1, 2, 2, 4, 1};
//     int B[] = {1, 2, 3, 4, 5, 6};
//     int D[] = {4, 4, 5, 6, 5, 3};
//     Init(7, A, B, D);
//     int X[] = {0, 6};
//     int Y[] = {3, 4};
//     cout << Query(2, X, 2, Y) << '\n';
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 217 ms 50768 KB Output is correct
3 Correct 213 ms 51284 KB Output is correct
4 Correct 217 ms 51248 KB Output is correct
5 Correct 236 ms 51584 KB Output is correct
6 Correct 157 ms 50256 KB Output is correct
7 Correct 224 ms 51112 KB Output is correct
8 Correct 216 ms 51364 KB Output is correct
9 Correct 237 ms 51580 KB Output is correct
10 Correct 168 ms 50344 KB Output is correct
11 Correct 213 ms 51112 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 2585 ms 199168 KB Output is correct
3 Correct 3756 ms 269172 KB Output is correct
4 Correct 942 ms 96484 KB Output is correct
5 Correct 5042 ms 341632 KB Output is correct
6 Correct 4005 ms 287604 KB Output is correct
7 Correct 1241 ms 97996 KB Output is correct
8 Correct 279 ms 75400 KB Output is correct
9 Correct 1226 ms 110920 KB Output is correct
10 Correct 947 ms 98808 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 45656 KB Output is correct
2 Correct 217 ms 50768 KB Output is correct
3 Correct 213 ms 51284 KB Output is correct
4 Correct 217 ms 51248 KB Output is correct
5 Correct 236 ms 51584 KB Output is correct
6 Correct 157 ms 50256 KB Output is correct
7 Correct 224 ms 51112 KB Output is correct
8 Correct 216 ms 51364 KB Output is correct
9 Correct 237 ms 51580 KB Output is correct
10 Correct 168 ms 50344 KB Output is correct
11 Correct 213 ms 51112 KB Output is correct
12 Correct 13 ms 45656 KB Output is correct
13 Correct 2585 ms 199168 KB Output is correct
14 Correct 3756 ms 269172 KB Output is correct
15 Correct 942 ms 96484 KB Output is correct
16 Correct 5042 ms 341632 KB Output is correct
17 Correct 4005 ms 287604 KB Output is correct
18 Correct 1241 ms 97996 KB Output is correct
19 Correct 279 ms 75400 KB Output is correct
20 Correct 1226 ms 110920 KB Output is correct
21 Correct 947 ms 98808 KB Output is correct
22 Correct 2955 ms 220648 KB Output is correct
23 Correct 3023 ms 224388 KB Output is correct
24 Correct 4869 ms 292656 KB Output is correct
25 Correct 4493 ms 294056 KB Output is correct
26 Correct 4177 ms 293732 KB Output is correct
27 Correct 5644 ms 369212 KB Output is correct
28 Correct 965 ms 121372 KB Output is correct
29 Correct 4258 ms 292356 KB Output is correct
30 Correct 4314 ms 293312 KB Output is correct
31 Correct 4282 ms 293164 KB Output is correct
32 Correct 1279 ms 111372 KB Output is correct
33 Correct 324 ms 75272 KB Output is correct
34 Correct 609 ms 91476 KB Output is correct
35 Correct 637 ms 92240 KB Output is correct
36 Correct 953 ms 96916 KB Output is correct
37 Correct 966 ms 97372 KB Output is correct