oj.uz

Submission #906103

# Submission time Handle Problem Language Result Execution time Memory
906103 2024-01-13T13:58:35 Z a_l_i_r_e_z_a Factories (JOI14_factories) C++17
100 / 100
 5359 ms 361436 KB 
// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 5e5 + 5;
const ll inf = 1e18 + 7;
int n, q, sz[maxn];
ll dist[maxn];
vector<pll> adj[maxn];
vector<pll> par[maxn];
bool mark[maxn];

void get_sz(int v, int p = -1){
    sz[v] = 1;
    for(auto [u, w]: adj[v]){
        if(u != p && !mark[u]){
            get_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

int find(int v, int s, int p = -1){
    for(auto [u, w]: adj[v]) if(u != p && !mark[u] && sz[u] * 2 > s) return find(u, s, v);
    return v;
}

void dfs(int v, int center, ll h = 0, int p = -1){
    par[v].pb(mp(center, h));
    for(auto [u, w]: adj[v]){
        if(!mark[u] && u != p) dfs(u, center, h +  w, v);
    }
}

void centroid_decomp(int v = 0){
    get_sz(v);
    v = find(v, sz[v]);
    dfs(v, v);
    mark[v] = 1;
    for(auto [u, w]: adj[v]) if(!mark[u]) centroid_decomp(u);
}

void turnOff(int v){
    for(auto [p, d]: par[v]) dist[p] = inf;
}

void turnOn(int v){
    for(auto [p, d]: par[v]) smin(dist[p], d);
}

ll get(int v){
    ll res = inf;
    for(auto [p, d]: par[v]) smin(res, d + dist[p]);
    return res;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    fill(dist, dist + n, inf);
    for(int i = 0; i < n - 1; i++){
        int u = A[i], v = B[i], w = D[i];
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    centroid_decomp();
}

ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) turnOn(X[i]);
    ll ans = inf;
    for(int i = 0; i < T; i++) smin(ans, get(Y[i]));
    for(int i = 0; i < S; i++) turnOff(X[i]);
    return ans;
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, q; cin >> n >> q;
//     fill(dist, dist + n, inf);
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         adj[u].pb(mp(v, w));
//         adj[v].pb(mp(u, w));
//     }
//     centroid_decomp();
//     while(q--){
//         int S, T; cin >> S >> T;
//         for(int i = 0; i < S; i++){
//             cin >> a[i];
//             turnOn(a[i]);
//         }
//         ll ans = inf;
//         for(int i = 0; i < T; i++){
//             int v; cin >> v;
//             smin(ans, get(v));
//         }
//         for(int i = 0; i < S; i++) turnOff(a[i]);
//         cout << ans << '\n';
//     }

//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 200 ms 50516 KB Output is correct
3 Correct 200 ms 51192 KB Output is correct
4 Correct 209 ms 51176 KB Output is correct
5 Correct 219 ms 51580 KB Output is correct
6 Correct 153 ms 50160 KB Output is correct
7 Correct 202 ms 51184 KB Output is correct
8 Correct 209 ms 51196 KB Output is correct
9 Correct 214 ms 51540 KB Output is correct
10 Correct 148 ms 50256 KB Output is correct
11 Correct 218 ms 51188 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 2415 ms 206360 KB Output is correct
3 Correct 3655 ms 287628 KB Output is correct
4 Correct 784 ms 109808 KB Output is correct
5 Correct 4761 ms 361436 KB Output is correct
6 Correct 4157 ms 287052 KB Output is correct
7 Correct 1151 ms 91028 KB Output is correct
8 Correct 286 ms 67168 KB Output is correct
9 Correct 1188 ms 104040 KB Output is correct
10 Correct 1131 ms 91380 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 200 ms 50516 KB Output is correct
3 Correct 200 ms 51192 KB Output is correct
4 Correct 209 ms 51176 KB Output is correct
5 Correct 219 ms 51580 KB Output is correct
6 Correct 153 ms 50160 KB Output is correct
7 Correct 202 ms 51184 KB Output is correct
8 Correct 209 ms 51196 KB Output is correct
9 Correct 214 ms 51540 KB Output is correct
10 Correct 148 ms 50256 KB Output is correct
11 Correct 218 ms 51188 KB Output is correct
12 Correct 13 ms 45656 KB Output is correct
13 Correct 2415 ms 206360 KB Output is correct
14 Correct 3655 ms 287628 KB Output is correct
15 Correct 784 ms 109808 KB Output is correct
16 Correct 4761 ms 361436 KB Output is correct
17 Correct 4157 ms 287052 KB Output is correct
18 Correct 1151 ms 91028 KB Output is correct
19 Correct 286 ms 67168 KB Output is correct
20 Correct 1188 ms 104040 KB Output is correct
21 Correct 1131 ms 91380 KB Output is correct
22 Correct 3155 ms 215692 KB Output is correct
23 Correct 3279 ms 219372 KB Output is correct
24 Correct 4888 ms 288260 KB Output is correct
25 Correct 4585 ms 290628 KB Output is correct
26 Correct 4550 ms 289500 KB Output is correct
27 Correct 5359 ms 361024 KB Output is correct
28 Correct 974 ms 113068 KB Output is correct
29 Correct 4220 ms 289052 KB Output is correct
30 Correct 4512 ms 289084 KB Output is correct
31 Correct 4512 ms 289124 KB Output is correct
32 Correct 1287 ms 104540 KB Output is correct
33 Correct 256 ms 67260 KB Output is correct
34 Correct 650 ms 84048 KB Output is correct
35 Correct 692 ms 85036 KB Output is correct
36 Correct 881 ms 90200 KB Output is correct
37 Correct 831 ms 90192 KB Output is correct