oj.uz

Submission #658904

# Submission time Handle Problem Language Result Execution time Memory
658904 2022-11-15T12:07:06 Z esomer Factories (JOI14_factories) C++17
100 / 100
 6147 ms 245856 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 12500 KB Output is correct
2 Correct 377 ms 21764 KB Output is correct
3 Correct 418 ms 31328 KB Output is correct
4 Correct 430 ms 25808 KB Output is correct
5 Correct 445 ms 27460 KB Output is correct
6 Correct 206 ms 27600 KB Output is correct
7 Correct 465 ms 27292 KB Output is correct
8 Correct 424 ms 27400 KB Output is correct
9 Correct 436 ms 27500 KB Output is correct
10 Correct 196 ms 27608 KB Output is correct
11 Correct 427 ms 27248 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 2544 ms 191820 KB Output is correct
3 Correct 3724 ms 205848 KB Output is correct
4 Correct 960 ms 219192 KB Output is correct
5 Correct 4814 ms 195644 KB Output is correct
6 Correct 3806 ms 207924 KB Output is correct
7 Correct 1655 ms 69280 KB Output is correct
8 Correct 400 ms 75952 KB Output is correct
9 Correct 1678 ms 69796 KB Output is correct
10 Correct 1584 ms 70744 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12500 KB Output is correct
2 Correct 377 ms 21764 KB Output is correct
3 Correct 418 ms 31328 KB Output is correct
4 Correct 430 ms 25808 KB Output is correct
5 Correct 445 ms 27460 KB Output is correct
6 Correct 206 ms 27600 KB Output is correct
7 Correct 465 ms 27292 KB Output is correct
8 Correct 424 ms 27400 KB Output is correct
9 Correct 436 ms 27500 KB Output is correct
10 Correct 196 ms 27608 KB Output is correct
11 Correct 427 ms 27248 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2544 ms 191820 KB Output is correct
14 Correct 3724 ms 205848 KB Output is correct
15 Correct 960 ms 219192 KB Output is correct
16 Correct 4814 ms 195644 KB Output is correct
17 Correct 3806 ms 207924 KB Output is correct
18 Correct 1655 ms 69280 KB Output is correct
19 Correct 400 ms 75952 KB Output is correct
20 Correct 1678 ms 69796 KB Output is correct
21 Correct 1584 ms 70744 KB Output is correct
22 Correct 3283 ms 217588 KB Output is correct
23 Correct 3479 ms 220168 KB Output is correct
24 Correct 5215 ms 214152 KB Output is correct
25 Correct 5194 ms 217952 KB Output is correct
26 Correct 5702 ms 214256 KB Output is correct
27 Correct 6147 ms 218068 KB Output is correct
28 Correct 1169 ms 245856 KB Output is correct
29 Correct 5131 ms 213900 KB Output is correct
30 Correct 5059 ms 213384 KB Output is correct
31 Correct 5007 ms 213984 KB Output is correct
32 Correct 1525 ms 70748 KB Output is correct
33 Correct 369 ms 76552 KB Output is correct
34 Correct 1069 ms 68124 KB Output is correct
35 Correct 1022 ms 68252 KB Output is correct
36 Correct 1377 ms 67528 KB Output is correct
37 Correct 1425 ms 67588 KB Output is correct