Submission #683201

#	Time	Username	Problem	Language	Result	Execution time	Memory
683201		LucaGreg	Factories (JOI14_factories)	C++17	100 / 100	6258 ms	180540 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

#define pb push_back
#define ll long long int
#define ff first
#define ss second

const ll INF = 1000000000000000000;

vector<int> adj[500010];
vector<int> weight[500010];

bool removed[500010];
int sub[500010];

int paiCentroid[500010];
pair<ll, int> minFactoryDist[500010];

int ancestor[500010][30];
ll nivel[500010];
int tin[500010], tout[500010];
int h = 0;
int tempo = 0;

int curQuery = 0;


void dfsInit(int cur, int pai){
    sub[cur] = 1;
    for(int i=0;i<(int)adj[cur].size();i++){
        int viz = adj[cur][i];
        if(removed[viz]) continue;
        if(viz==pai) continue;
        dfsInit(viz, cur);
        sub[cur] += sub[viz];
    }
}

int findCentroid(int cur, int pai, int size){
    for(int i=0;i<(int)adj[cur].size();i++){
        int viz = adj[cur][i];
        if(removed[viz]) continue;
        if(viz==pai) continue;
        if(sub[viz]>size/2) return findCentroid(viz, cur, size);
    }
    return cur;
}

void createCentroidTree(int cur, int centroidPai){
    dfsInit(cur, cur);
    int centroid = findCentroid(cur, cur, sub[cur]);
    
    paiCentroid[centroid] = centroidPai;
    removed[centroid] = true;
    
    for(int i=0;i<(int)adj[centroid].size();i++){
        int viz = adj[centroid][i];
        if(removed[viz]) continue;
        createCentroidTree(viz, centroid);
    }
}

void dfs(int cur, int pai){
    tempo++;
    tin[cur] = tempo;
    ancestor[cur][0] = pai;
    for(int i=1;i<=h;i++) ancestor[cur][i] = ancestor[ancestor[cur][i-1]][i-1];
    for(int i=0;i<(int)adj[cur].size();i++){
        int viz = adj[cur][i];
        int w = weight[cur][i];
        if(viz==pai) continue;
        nivel[viz] = nivel[cur] + w;
        dfs(viz, cur);
    }
    tout[cur] = tempo;
}

bool isAncestor(int a, int b){
    return tin[a]<=tin[b] && tout[b]<=tout[a];
}


int lca(int a, int b){
    if(isAncestor(a, b)) return a;
    if(isAncestor(b, a)) return b;
    for(int i=h;i>=0;i--) if(!isAncestor(ancestor[a][i], b)) a = ancestor[a][i];
    return ancestor[a][0];
}

ll calculaDist(int a, int b){
    int lca_ = lca(a, b);
    ll resp = abs(nivel[lca_] - nivel[a]) + abs(nivel[lca_] - nivel[b]);
    return resp;
}
 
void update(int v){
    int cur = v;
    while(cur!=-1){
        ll distancia = calculaDist(v, cur);
        if(minFactoryDist[cur].ss<curQuery){
            minFactoryDist[cur].ff = distancia;
            minFactoryDist[cur].ss = curQuery;
        }else{
            minFactoryDist[cur].ff = min(minFactoryDist[cur].ff, distancia);
        }
        cur = paiCentroid[cur];
    }
}

ll calculaMinFactoryDist(int v){
    int cur = v;
    ll resp = INF;
    while(cur!=-1){
        ll distancia = calculaDist(v, cur);
        if(minFactoryDist[cur].ss==curQuery) resp = min(resp, distancia + minFactoryDist[cur].ff);
        cur = paiCentroid[cur];
    }
    return resp;
}

void Init(int N, int A[], int B[], int D[]){
    for(int i=0;i<N-1;i++){
        int a = A[i], b = B[i], d = D[i];
        adj[a].pb(b);
        weight[a].pb(d);
        adj[b].pb(a);
        weight[b].pb(d);
    }
    nivel[0] = 0;
    h = ceil(log2(N));
    dfs(0, 0);
    createCentroidTree(0, -1);
}

long long Query(int S, int X[], int T, int Y[]){
    curQuery++;
    for(int i=0;i<S;i++) update(X[i]);
    ll resp = INF;
    for(int i=0;i<T;i++) resp = min(resp, calculaMinFactoryDist(Y[i]));
    return resp;
}

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