oj.uz

Submission #683201

# Submission time Handle Problem Language Result Execution time Memory
683201 2023-01-17T22:59:40 Z LucaGreg Factories (JOI14_factories) C++17
100 / 100
 6258 ms 180540 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24436 KB Output is correct
2 Correct 451 ms 34144 KB Output is correct
3 Correct 864 ms 34184 KB Output is correct
4 Correct 680 ms 34124 KB Output is correct
5 Correct 512 ms 34408 KB Output is correct
6 Correct 194 ms 33948 KB Output is correct
7 Correct 834 ms 33904 KB Output is correct
8 Correct 832 ms 33676 KB Output is correct
9 Correct 534 ms 33940 KB Output is correct
10 Correct 196 ms 33612 KB Output is correct
11 Correct 816 ms 33644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24020 KB Output is correct
2 Correct 2123 ms 148016 KB Output is correct
3 Correct 3453 ms 149812 KB Output is correct
4 Correct 788 ms 150420 KB Output is correct
5 Correct 3325 ms 180540 KB Output is correct
6 Correct 3759 ms 151152 KB Output is correct
7 Correct 2196 ms 57124 KB Output is correct
8 Correct 331 ms 58036 KB Output is correct
9 Correct 1282 ms 61736 KB Output is correct
10 Correct 2145 ms 58436 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24436 KB Output is correct
2 Correct 451 ms 34144 KB Output is correct
3 Correct 864 ms 34184 KB Output is correct
4 Correct 680 ms 34124 KB Output is correct
5 Correct 512 ms 34408 KB Output is correct
6 Correct 194 ms 33948 KB Output is correct
7 Correct 834 ms 33904 KB Output is correct
8 Correct 832 ms 33676 KB Output is correct
9 Correct 534 ms 33940 KB Output is correct
10 Correct 196 ms 33612 KB Output is correct
11 Correct 816 ms 33644 KB Output is correct
12 Correct 16 ms 24020 KB Output is correct
13 Correct 2123 ms 148016 KB Output is correct
14 Correct 3453 ms 149812 KB Output is correct
15 Correct 788 ms 150420 KB Output is correct
16 Correct 3325 ms 180540 KB Output is correct
17 Correct 3759 ms 151152 KB Output is correct
18 Correct 2196 ms 57124 KB Output is correct
19 Correct 331 ms 58036 KB Output is correct
20 Correct 1282 ms 61736 KB Output is correct
21 Correct 2145 ms 58436 KB Output is correct
22 Correct 3281 ms 149316 KB Output is correct
23 Correct 2912 ms 151688 KB Output is correct
24 Correct 6223 ms 151588 KB Output is correct
25 Correct 5898 ms 155184 KB Output is correct
26 Correct 6081 ms 151768 KB Output is correct
27 Correct 4689 ms 177656 KB Output is correct
28 Correct 1010 ms 154544 KB Output is correct
29 Correct 6258 ms 151268 KB Output is correct
30 Correct 5858 ms 150656 KB Output is correct
31 Correct 6069 ms 151456 KB Output is correct
32 Correct 1503 ms 62756 KB Output is correct
33 Correct 360 ms 58576 KB Output is correct
34 Correct 1266 ms 55268 KB Output is correct
35 Correct 1340 ms 55044 KB Output is correct
36 Correct 2356 ms 55756 KB Output is correct
37 Correct 2569 ms 55680 KB Output is correct