Submission #116447

#	Time	Username	Problem	Language	Result	Execution time	Memory
116447		YazanZk	Factories (JOI14_factories)	C++14	15 / 100	8090 ms	389616 KiB

factories

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

/***************  LCA  ******************/

const int N = 5 * 1e5 + 1 ;
const int Log = 21;
const ll inf = 1e18 ;

int n ;
int P[N][Log], L[N] ;
ll cost[N];
vector < pair < int , int > > G[N];

void dfs(int u, int p, int d , ll w) {
    P[u][0] = p ;
    L[u] = d ;
    cost[u] = w;
    for(auto e : G[u]) {
        int v = e.first , c = e.second ;
        if(v == p)
            continue ;
        dfs(v, u, d + 1, w + c);
    }
}

void dp() {

    for(int i = 0 ; i < n ; i++)
        for(int j = 1 ; (1 << j) < n ; j++)
            P[i][j] = -1 ;

    for(int j = 1 ; (1 << j) < n ; j++)
        for(int i = 0 ; i < n ; i++)
            if(P[i][j - 1] != -1)
                P[i][j] = P[P[i][j - 1]][j - 1] ;
}

int lca(int u, int v) {

    if(L[u] < L[v])
        swap(u, v);

    int i, log ;
    for(log = 1 ; (1 << log) <= L[u] ; log++);
    log -- ;

    for(i = log ; i >= 0 ; i--) {
        if(L[u] - (1 << i) >= L[v])
            u = P[u][i] ;
    }

    if(u == v)
        return u ;

    for(i = log ; i >= 0 ; i--) {
        if(P[u][i] != -1 && P[u][i] != P[v][i])
            u = P[u][i], v = P[v][i] ;
    }

    return P[u][0];
}

ll dist(int u, int v) {
    return cost[u] + cost[v] - 2 * cost[lca(u, v)];
}

/*************** Centroid ******************/

int sub[N], par[N];
bool blocked[N];
vector < pair < int , int > > tree[N];

void get_size(int u, int p) {
    par[u] = p ;
    sub[u] = 1 ;
    for(auto e : G[u]) {
        int v = e.first ;
        if(v == p || blocked[v])
            continue ;
        get_size(v, u);
        sub[u] += sub[v];
    }
}

int get_centroid(int src) {

    get_size(src, src);

    int centroid = src, best = sub[src] ;
    queue < int > Q ;
    Q.emplace(src);

    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();

        int size = sub[src] - sub[u];
        for(auto e : G[u]) {
            int v = e.first;
            if(v == par[u] || blocked[v])
                continue ;
            Q.emplace(v);
            size = max(size, sub[v]);
        }

        if(best > size) {
            best = size;
            centroid = u ;
        }
    }

    blocked[centroid] = true;

    for(auto e : G[centroid]) {
        int v = e.first ;
        if(blocked[v]) continue ;
        int child = get_centroid(v);
        tree[centroid].push_back({child , 0});
        tree[child].push_back({centroid , 0});
    }

    return centroid ;
}

ll ans[N];
unordered_map < int , ll > dis[N];

void update(int u){
    int v = u ;
    while(true){
         if(ans[v] != -1) ans[v] = min(ans[v] , dis[v][u]);
         else ans[v] = dis[v][u];
         if(v == par[v]) break ;
         v = par[v];
    }
}

ll query(int u){
   int v = u ;
   ll ret = inf ;
   while(true){
        if(ans[v] != -1) ret = min(ret , ans[v] + dis[v][u]);
        if(v == par[v]) break ;
        v = par[v];
   }
   return ret;
}


ll Query(int S , int X[] , int T , int Y[]){

    memset(ans , -1 , sizeof ans);

   for(int i = 0 ; i < T ; i++){
         update(Y[i]);
   }

   ll ret = inf ;
   for(int i = 0 ; i < S ; i++){
        ret = min(ret,  query(X[i]));
   }

   return ret;
}

void Init(int N , int A[] , int B[] , int D[]){
     n = N ;
     for(int i = 0 ; i < n - 1 ; i++){
           int u = A[i] , v = B[i] , w = D[i];
           G[u].push_back({v , w});
           G[v].push_back({u , w});
     }

     dfs(0 , -1 , 0 , 0);
     dp();
     int root = get_centroid(0);
     memset(blocked , 0 , sizeof blocked);
     swap(tree , G);
     get_size(root , root);

     for(int i = 0 ; i < n ; i++){
           int v = i ;
           while(true){
                dis[v][i] = dist(v , i);
               if(v == par[v]) break ;
               v = par[v];
           }
     }
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67