제출 #683197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683197		LucaGreg	공장들 (JOI14_factories)	C++17	15 / 100	864 ms	33352 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[100010];
vector<int> weight[100010];

bool removed[100010];
int sub[100010];

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

int ancestor[100010][30];
ll nivel[100010];
int tin[100010], tout[100010];
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]);
    //for(int i=0;i<7;i++) printf("%d %d %d %d\n", i, nivel[i], minFactoryDist[i].ff, minFactoryDist[i].ss);
    ll resp = INF;
    for(int i=0;i<T;i++) resp = min(resp, calculaMinFactoryDist(Y[i]));
    return resp;
}

/*int main()
{
    int n, q; scanf("%d %d", &n, &q);
    int a[100010], b[100010], d[100010];
    for(int i=0;i<n-1;i++) scanf("%d %d %d", &a[i], &b[i], &d[i]);
    Init(n, a, b, d);
    for(int i=0;i<q;i++){
        int s, t; scanf("%d %d", &s, &t);
        int x[10010], y[10010];
        for(int j=0;j<s;j++) scanf("%d", &x[j]);
        for(int j=0;j<t;j++) scanf("%d", &y[j]);
        printf("%lld\n", Query(s, x, t, y));
    }
    
    return 0;
}*/

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