oj.uz

Submission #658772

# Submission time Handle Problem Language Result Execution time Memory
658772 2022-11-14T21:26:19 Z esomer Factories (JOI14_factories) C++17
100 / 100
 6092 ms 227344 KB 
#include<bits/stdc++.h>
#include "factories.h"

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;
const int maxN = 500001;
const int maxEuler = 3000000;
const int maxlog = 20;

int sparse[maxEuler][23];
int euler[maxEuler];
int lb[maxEuler];
pair<int, int> t[maxN];
ll dists[maxN];
int depths[maxN];
vector<pair<int, ll>> adj[maxN];
bool done[maxN];
int subtree_size[maxN];
int parents[maxN];
ll ans[maxN];
int centr;
int root;
int cnt;

void DFS_lca(int x, int p){
    t[x].first = cnt;
    euler[cnt] = x; cnt++;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node != p){
            depths[node] = depths[x] + 1;
            dists[node] = dists[x] + pr.second;
            DFS_lca(node, x);
            t[x].second = cnt;
            euler[cnt] = x; cnt++;
        }
    }
    if(t[x].first + 1 == cnt){
        t[x].second = cnt;
        euler[cnt] = x; cnt++;
    }
}

void build_lca(int n){
    depths[0] = 0;
    dists[0] = 0;
    cnt = 0;
    DFS_lca(0, -1);
    for(int i = 0; i < 23; i++){
        for(int j = 0; j < cnt; j++){
            if(i > 0){
                if(depths[sparse[j][i - 1]] < depths[sparse[max(0, j - (1<<(i - 1)))][i - 1]]){
                    sparse[j][i] = sparse[j][i - 1];
                }else sparse[j][i] = sparse[max(0, j - (1<<(i - 1)))][i - 1];
            }
            else sparse[j][i] = euler[j];
        }
    }
    ll pw = 1;
    int curr = 0;
    for(int i = 1; i < cnt; i++){
        if(i == pw * 2){
            pw *= 2; curr++;
        }
        lb[i] = curr;
    }
}

int lca(int a, int b){
    if(a == b) return a;
    int l = min(t[a].first, t[b].first); int r = max(t[a].second, t[b].second);
    int dst = r - l + 1;
    if(depths[sparse[r][lb[dst]]] < depths[sparse[l + (1 << lb[dst]) - 1][lb[dst]]]) return sparse[r][lb[dst]];
    else return sparse[l + (1 << lb[dst]) - 1][lb[dst]];
}

ll dist(int a, int b){
    int anc = lca(a, b);
    return dists[a] + dists[b] - 2 * dists[anc];
}

int find_size(int x, int par){
    subtree_size[x] = 1;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == par || done[node] == 1) continue;
        subtree_size[x] += find_size(node,  x);
    }
    return subtree_size[x];
}

void find_centroid(int x, int par, int siz){
    bool good = 1;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == par || done[node] == 1) continue;
        if(subtree_size[node] > siz / 2){
            find_centroid(node, x, siz);
            good = 0;
        }
    }
    if(good) centr = x;
}

void build(int n){
    queue<pair<int, int>> q;
    q.push({0, -1});
    while(!q.empty()){
        int x = q.front().first; int par = q.front().second; q.pop();
        int siz = find_size(x, -1);
        centr = -1;
        find_centroid(x, -1, siz);
        if(par == -1) root = centr;
        parents[centr] = par;
        done[centr] = 1;
        for(auto pr : adj[centr]){
            int node = pr.first;
            if(!done[node]) q.push({node, centr});
        }
    }
}

void add(int x){
    int next = x;
    while(next != -1){
        ll d = dist(next, x);
        ans[next] = min(ans[next], d);
        next = parents[next];
    }
}

void rmv(int x){
    int next = x;
    while(next != -1){
        ans[next] = 1e18;
        next = parents[next];
    }
}

ll query(int x){
    int next = x;
    ll rep = 1e18;
    while(next != -1){
        ll d = dist(next, x);
        rep = min(rep, ans[next] + d);
        next = parents[next];
    }
    return rep;
}

void Init(int N, int A[], int B[], int D[]){
    for(int i = 0; i < N - 1; i++){
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    build_lca(N);
    build(N);
    for(int i = 0; i < N; i++) ans[i] = 1e18;
}

ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) add(X[i]);
    ll retrn = 1e18;
    for(int i = 0; i < T; i++) retrn = min(retrn, query(Y[i]));
    for(int i = 0; i < S; i++) rmv(X[i]);
    return retrn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 317 ms 22668 KB Output is correct
3 Correct 414 ms 22688 KB Output is correct
4 Correct 391 ms 24200 KB Output is correct
5 Correct 461 ms 25572 KB Output is correct
6 Correct 199 ms 25780 KB Output is correct
7 Correct 407 ms 25624 KB Output is correct
8 Correct 431 ms 25580 KB Output is correct
9 Correct 456 ms 25560 KB Output is correct
10 Correct 191 ms 25804 KB Output is correct
11 Correct 388 ms 25500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2498 ms 192696 KB Output is correct
3 Correct 3777 ms 189180 KB Output is correct
4 Correct 915 ms 218560 KB Output is correct
5 Correct 4666 ms 195632 KB Output is correct
6 Correct 3814 ms 207976 KB Output is correct
7 Correct 1521 ms 69144 KB Output is correct
8 Correct 384 ms 76012 KB Output is correct
9 Correct 1590 ms 69776 KB Output is correct
10 Correct 1355 ms 70732 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 317 ms 22668 KB Output is correct
3 Correct 414 ms 22688 KB Output is correct
4 Correct 391 ms 24200 KB Output is correct
5 Correct 461 ms 25572 KB Output is correct
6 Correct 199 ms 25780 KB Output is correct
7 Correct 407 ms 25624 KB Output is correct
8 Correct 431 ms 25580 KB Output is correct
9 Correct 456 ms 25560 KB Output is correct
10 Correct 191 ms 25804 KB Output is correct
11 Correct 388 ms 25500 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2498 ms 192696 KB Output is correct
14 Correct 3777 ms 189180 KB Output is correct
15 Correct 915 ms 218560 KB Output is correct
16 Correct 4666 ms 195632 KB Output is correct
17 Correct 3814 ms 207976 KB Output is correct
18 Correct 1521 ms 69144 KB Output is correct
19 Correct 384 ms 76012 KB Output is correct
20 Correct 1590 ms 69776 KB Output is correct
21 Correct 1355 ms 70732 KB Output is correct
22 Correct 3318 ms 199508 KB Output is correct
23 Correct 3388 ms 202000 KB Output is correct
24 Correct 4980 ms 196192 KB Output is correct
25 Correct 5107 ms 202452 KB Output is correct
26 Correct 5047 ms 196264 KB Output is correct
27 Correct 6092 ms 201460 KB Output is correct
28 Correct 1134 ms 227344 KB Output is correct
29 Correct 4976 ms 196920 KB Output is correct
30 Correct 4796 ms 203836 KB Output is correct
31 Correct 4991 ms 196880 KB Output is correct
32 Correct 1490 ms 70824 KB Output is correct
33 Correct 370 ms 76404 KB Output is correct
34 Correct 1037 ms 68028 KB Output is correct
35 Correct 1014 ms 68132 KB Output is correct
36 Correct 1459 ms 67516 KB Output is correct
37 Correct 1362 ms 67628 KB Output is correct