oj.uz

Submission #767765

# Submission time Handle Problem Language Result Execution time Memory
767765 2023-06-27T07:03:53 Z Abrar_Al_Samit Factories (JOI14_factories) C++17
15 / 100
 8000 ms 139984 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int nax = 5e5 + 3;
const int lg = 20;

vector<pair<int, int>>g[nax];
int CT_par[nax];

int st[nax], en[nax], tt = 0;
int up[nax][lg];
long long d[nax];
int sub[nax];

void dfs(int v, int p) {
    st[v] = tt++;
    up[v][0] = p;

    for(int j=1; j<lg; ++j) {
        up[v][j] = up[up[v][j-1]][j-1];
    }

    for(auto [u, w] : g[v]) if(u!=p) {
        d[u] = d[v] + w;
        dfs(u, v);
    }
    en[v] = tt-1;
}

bool ban[nax];

int cdfs(int v, int p = -1) {
    sub[v] = 1;
    for(auto [u, w] : g[v]) if(u!=p && !ban[u]) {
        sub[v] += cdfs(u, v);
    }
    return sub[v];
}
int get_centroid(int v, int sz, int p = -1) {
    for(auto [u, w] : g[v]) if(sub[u]*2>sz && u!=p && !ban[u]) {
        return get_centroid(u, sz, v);
    }
    return v;
}
void centroid(int v, int prevCen = -1) {
    int C = get_centroid(v, cdfs(v));

    CT_par[C] = prevCen;

    ban[C] = 1;
    for(auto [u, w] : g[C]) if(!ban[u]) {
        centroid(u, C);
    }
}

bool is_anc(int u, int v) {
    return st[u]<=st[v] && en[u]>=en[v];
}
int getLCA(int u, int v) {
    for(int j=lg-1; j>=0; --j) if(!is_anc(up[u][j], v)) {
        u = up[u][j];
    }
    if(!is_anc(u, v)) u = up[u][0];
    return u;
}
long long get_dist(int u, int v) {
    int lca = getLCA(u, v);
    return d[u] + d[v] - 2 * d[lca];
}
long long ans[nax];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N; ++i) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }

    dfs(0, 0);
    centroid(0);

    for(int i=0; i<N; ++i) {
        ans[i] = 1e18;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; ++i) {
        int v = X[i];

        int u = v;
        while(u!=-1) {
            ans[u] = min(ans[u], get_dist(u, v));
            u = CT_par[u];
        }
    }

    long long ret = 1e18;

    for(int i=0; i<T; ++i) {
        int v = Y[i];

        int u = v;
        while(u!=-1) {
            ret = min(ret, ans[u] + get_dist(u, v));
            u = CT_par[u];
        }
    }

    for(int i=0; i<S; ++i) {
        int v = X[i];

        int u = v;
        while(u!=-1) {
            ans[u] = 1e18;
            u = CT_par[u];
        }
    }
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 12636 KB Output is correct
2 Correct 1816 ms 30316 KB Output is correct
3 Correct 2553 ms 30360 KB Output is correct
4 Correct 2504 ms 30368 KB Output is correct
5 Correct 3177 ms 30672 KB Output is correct
6 Correct 754 ms 30428 KB Output is correct
7 Correct 2555 ms 30388 KB Output is correct
8 Correct 2639 ms 30364 KB Output is correct
9 Correct 3212 ms 30560 KB Output is correct
10 Correct 790 ms 30348 KB Output is correct
11 Correct 2542 ms 30496 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12244 KB Output is correct
2 Correct 3269 ms 117516 KB Output is correct
3 Correct 7510 ms 118312 KB Output is correct
4 Correct 1115 ms 117912 KB Output is correct
5 Execution timed out 8013 ms 139984 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 12636 KB Output is correct
2 Correct 1816 ms 30316 KB Output is correct
3 Correct 2553 ms 30360 KB Output is correct
4 Correct 2504 ms 30368 KB Output is correct
5 Correct 3177 ms 30672 KB Output is correct
6 Correct 754 ms 30428 KB Output is correct
7 Correct 2555 ms 30388 KB Output is correct
8 Correct 2639 ms 30364 KB Output is correct
9 Correct 3212 ms 30560 KB Output is correct
10 Correct 790 ms 30348 KB Output is correct
11 Correct 2542 ms 30496 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 3269 ms 117516 KB Output is correct
14 Correct 7510 ms 118312 KB Output is correct
15 Correct 1115 ms 117912 KB Output is correct
16 Execution timed out 8013 ms 139984 KB Time limit exceeded
17 Halted 0 ms 0 KB -