Submission #658989

#	Time	Username	Problem	Language	Result	Execution time	Memory
658989		esomer	Factories (JOI14_factories)	C++17	100 / 100	3609 ms	299292 KiB

factories

#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 = 2500000;
const int maxlog = 20;

int sparse[maxEuler][23];
int euler[maxEuler];
int lb[maxEuler];
pair<int, int> t[maxN];
ll dists[maxN];
ll dist_parent[maxN][maxlog + 1];
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;
    }
}

ll dist(int a, int b){
    if(a == b) return 0;
    int anc;
    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]]]) anc = sparse[r][lb[dst]];
    else anc = sparse[l + (1 << lb[dst]) - 1][lb[dst]];
    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 x, int par){
    int siz = find_size(x, -1);
    centr = -1;
    find_centroid(x, -1, siz);
    parents[centr] = par;
    done[centr] = 1;
    int mine = centr;
    for(auto pr : adj[mine]){
        int node = pr.first;
        if(!done[node]) build(node, mine);
    }
}

void st(int x){
    int next = x;
    int curr = 0;
    while(next != -1){
        dist_parent[x][curr] = dist(x, next);
        next = parents[next];
        curr++;
    }
}

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

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;
    int curr = 0;
    while(next != -1){
        ll d = dist_parent[x][curr];
        rep = min(rep, ans[next] + d);
        next = parents[next];
        curr++;
    }
    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(0, -1);
    for(int i = 0; i < N; i++) {ans[i] = 1e18; st(i);}
}

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67