oj.uz

Submission #993828

# Submission time Handle Problem Language Result Execution time Memory
993828 2024-06-06T13:25:22 Z Albertstein Factories (JOI14_factories) C++17
100 / 100
 2867 ms 356848 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 500001, INF = LLONG_MAX / 3;
bool rem[maxn];
int sub_sz[maxn];
long long mini[maxn];
vector <pair<int, long long> > Dist[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

void dfs2(int u, int p, long long dist, int r){
    Dist[u].push_back({r, dist});
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            dfs2(v, u, dist + d, r);
        }
    }
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int sz = dfs(r);
    int c = g_cen(r, sz);
    dfs2(c, -1, 0, c);
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            sol(v);
        }
    }
    return c;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    for(int i = 0; i < N; i++) {mini[i] = INF;}
    sol();
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    vector <int> q;
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [v, d] : Dist[x]){
            mini[v] = min(mini[v], d);
            q.push_back(v);
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        for(auto [v, d] : Dist[y]){
            ans = min(ans, mini[v] + d);
        }
    }//*/
    for(auto x : q) {mini[x] = INF;}
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43608 KB Output is correct
2 Correct 191 ms 54284 KB Output is correct
3 Correct 200 ms 54612 KB Output is correct
4 Correct 221 ms 55008 KB Output is correct
5 Correct 265 ms 55172 KB Output is correct
6 Correct 145 ms 53692 KB Output is correct
7 Correct 200 ms 54608 KB Output is correct
8 Correct 213 ms 54804 KB Output is correct
9 Correct 229 ms 55168 KB Output is correct
10 Correct 146 ms 53584 KB Output is correct
11 Correct 200 ms 54612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43608 KB Output is correct
2 Correct 1302 ms 198968 KB Output is correct
3 Correct 1975 ms 283212 KB Output is correct
4 Correct 539 ms 110424 KB Output is correct
5 Correct 2614 ms 355608 KB Output is correct
6 Correct 2086 ms 283476 KB Output is correct
7 Correct 561 ms 91640 KB Output is correct
8 Correct 259 ms 69312 KB Output is correct
9 Correct 655 ms 104628 KB Output is correct
10 Correct 521 ms 92548 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43608 KB Output is correct
2 Correct 191 ms 54284 KB Output is correct
3 Correct 200 ms 54612 KB Output is correct
4 Correct 221 ms 55008 KB Output is correct
5 Correct 265 ms 55172 KB Output is correct
6 Correct 145 ms 53692 KB Output is correct
7 Correct 200 ms 54608 KB Output is correct
8 Correct 213 ms 54804 KB Output is correct
9 Correct 229 ms 55168 KB Output is correct
10 Correct 146 ms 53584 KB Output is correct
11 Correct 200 ms 54612 KB Output is correct
12 Correct 7 ms 43608 KB Output is correct
13 Correct 1302 ms 198968 KB Output is correct
14 Correct 1975 ms 283212 KB Output is correct
15 Correct 539 ms 110424 KB Output is correct
16 Correct 2614 ms 355608 KB Output is correct
17 Correct 2086 ms 283476 KB Output is correct
18 Correct 561 ms 91640 KB Output is correct
19 Correct 259 ms 69312 KB Output is correct
20 Correct 655 ms 104628 KB Output is correct
21 Correct 521 ms 92548 KB Output is correct
22 Correct 1641 ms 218072 KB Output is correct
23 Correct 1685 ms 224580 KB Output is correct
24 Correct 2473 ms 292964 KB Output is correct
25 Correct 2436 ms 291580 KB Output is correct
26 Correct 2386 ms 280480 KB Output is correct
27 Correct 2867 ms 356848 KB Output is correct
28 Correct 545 ms 110004 KB Output is correct
29 Correct 2281 ms 279412 KB Output is correct
30 Correct 2228 ms 280080 KB Output is correct
31 Correct 2329 ms 279968 KB Output is correct
32 Correct 736 ms 107388 KB Output is correct
33 Correct 225 ms 66308 KB Output is correct
34 Correct 386 ms 81572 KB Output is correct
35 Correct 430 ms 82496 KB Output is correct
36 Correct 498 ms 87124 KB Output is correct
37 Correct 531 ms 87120 KB Output is correct