oj.uz

Submission #658903

# Submission time Handle Problem Language Result Execution time Memory
658903 2022-11-15T12:05:07 Z esomer Factories (JOI14_factories) C++17
0 / 100
 8000 ms 207804 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 x, int par){
    int siz = find_size(x, -1);
    centr = -1;
    find_centroid(x, -1, siz);
    parents[centr] = par;
    done[centr] = 1;
    for(auto pr : adj[centr]){
        int node = pr.first;
        if(!done[node]) build(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(0, -1);
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 12748 KB Output is correct
2 Execution timed out 8004 ms 31320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12372 KB Output is correct
2 Execution timed out 8051 ms 207804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 12748 KB Output is correct
2 Execution timed out 8004 ms 31320 KB Time limit exceeded
3 Halted 0 ms 0 KB -