oj.uz

Submission #993795

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

const long long maxn = 500001, 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 143 ms 16440 KB Output is correct
2 Correct 1455 ms 42124 KB Output is correct
3 Correct 2148 ms 47172 KB Output is correct
4 Correct 2070 ms 47164 KB Output is correct
5 Correct 2471 ms 47400 KB Output is correct
6 Correct 1122 ms 47184 KB Output is correct
7 Correct 2197 ms 46968 KB Output is correct
8 Correct 2165 ms 47188 KB Output is correct
9 Correct 2502 ms 47396 KB Output is correct
10 Correct 1163 ms 47188 KB Output is correct
11 Correct 2047 ms 47108 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 37468 KB Output is correct
2 Execution timed out 8031 ms 115792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 16440 KB Output is correct
2 Correct 1455 ms 42124 KB Output is correct
3 Correct 2148 ms 47172 KB Output is correct
4 Correct 2070 ms 47164 KB Output is correct
5 Correct 2471 ms 47400 KB Output is correct
6 Correct 1122 ms 47184 KB Output is correct
7 Correct 2197 ms 46968 KB Output is correct
8 Correct 2165 ms 47188 KB Output is correct
9 Correct 2502 ms 47396 KB Output is correct
10 Correct 1163 ms 47188 KB Output is correct
11 Correct 2047 ms 47108 KB Output is correct
12 Correct 100 ms 37468 KB Output is correct
13 Execution timed out 8031 ms 115792 KB Time limit exceeded
14 Halted 0 ms 0 KB -