oj.uz

Submission #993791

# Submission time Handle Problem Language Result Execution time Memory
993791 2024-06-06T12:32:03 Z Albertstein Factories (JOI14_factories) C++17
15 / 100
 1532 ms 61344 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 5001, mbit = 20, INF = LLONG_MAX / 3;
int n;
bool rem[maxn];
int sub_sz[maxn];
int stp[maxn][mbit];
int dth[maxn];
long long dst[maxn];
int cen[maxn];
long long mini[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int c = g_cen(r, dfs(r));
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            cen[sol(v)] = c;
        }
    }
    return c;
}

void LCA_dfs(int u){
    for(int i = 1; i < mbit; i++){
        stp[u][i] = stp[stp[u][i - 1]][i - 1];
    }
    for(auto [v, d] : G[u]){
        if(v != stp[u][0]){
            stp[v][0] = u;
            dth[v] = dth[u] + 1;
            dst[v] = dst[u] + d;
            LCA_dfs(v);
        }
    }
}

int LCA(int u, int v){
    if(dth[u] < dth[v]) swap(u, v);
    for(int i = mbit - 1; i >= 0; i--){
        if(dth[u] - dth[v] >= (1<<i)){
            u = stp[u][i];
        }
    }
    if(u == v) return u;
    for(int i = mbit - 1; i >= 0; i--){
        if(stp[u][i] != stp[v][i]){
            u = stp[u][i];
            v = stp[v][i];
        }
    }
    return stp[u][0];
}

long long Dist(int u, int v){
    int c = LCA(u, v);
    return dst[u] + dst[v] - 2 * dst[c];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    cen[sol()] = -1;
    LCA_dfs(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    fill(mini, mini + maxn, INF);
    for(int i = 0; i < S; i++){
        int x = X[i];
        int v = x;
        while(v != -1){
            mini[v] = min(mini[v], Dist(x, v));
            v = cen[v];
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        int v = y;
        while(v != -1){
            ans = min(ans, mini[v] + Dist(y, v));
            v = cen[v];
        }
    }//*/
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19288 KB Output is correct
2 Correct 627 ms 32808 KB Output is correct
3 Correct 1243 ms 32852 KB Output is correct
4 Correct 1170 ms 32676 KB Output is correct
5 Correct 1471 ms 33108 KB Output is correct
6 Correct 231 ms 32852 KB Output is correct
7 Correct 1181 ms 32812 KB Output is correct
8 Correct 1302 ms 32824 KB Output is correct
9 Correct 1532 ms 33036 KB Output is correct
10 Correct 276 ms 32816 KB Output is correct
11 Correct 1268 ms 32852 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Runtime error 231 ms 61344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19288 KB Output is correct
2 Correct 627 ms 32808 KB Output is correct
3 Correct 1243 ms 32852 KB Output is correct
4 Correct 1170 ms 32676 KB Output is correct
5 Correct 1471 ms 33108 KB Output is correct
6 Correct 231 ms 32852 KB Output is correct
7 Correct 1181 ms 32812 KB Output is correct
8 Correct 1302 ms 32824 KB Output is correct
9 Correct 1532 ms 33036 KB Output is correct
10 Correct 276 ms 32816 KB Output is correct
11 Correct 1268 ms 32852 KB Output is correct
12 Correct 5 ms 19036 KB Output is correct
13 Runtime error 231 ms 61344 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -