oj.uz

Submission #516477

# Submission time Handle Problem Language Result Execution time Memory
516477 2022-01-21T11:49:27 Z Jomnoi Factories (JOI14_factories) C++17
15 / 100
 8000 ms 117368 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define DEBUG 0
using namespace std;

const int MX = 5e5 + 10;
const int B = 20;
const long long INF = 1e18 + 7;

vector <pair <int, int>> adj[MX];
int depth[MX], parent[MX][B];
long long dist[MX], ans[MX];
int sz[MX], ancestor[MX];
bool deleted[MX];

void compute_lca(const int &u, const int &p) {
    for(int i = 1; i < B; i++) {
        parent[u][i] = parent[parent[u][i - 1]][i - 1];
    }
    for(auto [v, w] : adj[u]) {
        if(v == p) {
            continue;
        }

        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        parent[v][0] = u;
        compute_lca(v, u);
    }
}

int find_size(const int &u, const int &p) {
    sz[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(v == p or deleted[v] == true) {
            continue;
        }
        
        sz[u] += find_size(v, u);
    }
    return sz[u];
}

int find_centroid(const int &u, const int &p, const int &n) {
    for(auto [v, w] : adj[u]) {
        if(v == p or deleted[v] == true) {
            continue;
        }

        if(sz[v] > n / 2) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void build_centroid(const int &u, const int &p) {
    int c = find_centroid(u, -1, find_size(u, -1));
    deleted[c] = true;
    ancestor[c] = p;
    for(auto [v, w] : adj[c]) {
        if(deleted[v] == false) {
            build_centroid(v, c);
        }
    }
}

long long get(const int &a, const int &b) {
    int u = a, v = b;

    if(depth[u] < depth[v]) {
        swap(u, v);
    }
    for(int i = B - 1; i >= 0; i--) {
        if(depth[parent[u][i]] >= depth[v]) {
            u = parent[u][i];
        }
    }
    for(int i = B - 1; i >= 0; i--) {
        if(parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    if(u != v) {
        u = parent[u][0];
    }

    return dist[a] + dist[b] - 2 * dist[u];
}

void reset(const int &u) {
    int a = u;
    while(a != -1) {
        ans[a] = INF;
        a = ancestor[a];
    }
}

void update(const int &u) {
    int a = u;
    while(a != -1) {
        ans[a] = min(ans[a], get(u, a));
        a = ancestor[a];
    }
}

long long query(const int &u) {
    int a = u;
    long long res = INF;
    while(a != -1) {
        res = min(res, ans[a] + get(u, a));
        a = ancestor[a];
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; i++) {
        update(X[i] + 1);
    }
    
    long long ans = INF;
    for(int i = 0; i < T; i++) {
        ans = min(ans, query(Y[i] + 1));
    }

    for(int i = 0; i < S; i++) {
        reset(X[i] + 1);
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++) {
        A[i]++, B[i]++;
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    depth[0] = -1;
    compute_lca(1, -1);
    build_centroid(1, -1);
    for(int i = 1; i <= N; i++) {
        ans[i] = INF;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12620 KB Output is correct
2 Correct 3102 ms 30292 KB Output is correct
3 Correct 4549 ms 30276 KB Output is correct
4 Correct 4520 ms 30512 KB Output is correct
5 Correct 5617 ms 30680 KB Output is correct
6 Correct 1065 ms 30248 KB Output is correct
7 Correct 4527 ms 30380 KB Output is correct
8 Correct 4729 ms 30308 KB Output is correct
9 Correct 5627 ms 30648 KB Output is correct
10 Correct 1067 ms 30260 KB Output is correct
11 Correct 4577 ms 30408 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12292 KB Output is correct
2 Correct 5022 ms 115516 KB Output is correct
3 Execution timed out 8083 ms 117368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12620 KB Output is correct
2 Correct 3102 ms 30292 KB Output is correct
3 Correct 4549 ms 30276 KB Output is correct
4 Correct 4520 ms 30512 KB Output is correct
5 Correct 5617 ms 30680 KB Output is correct
6 Correct 1065 ms 30248 KB Output is correct
7 Correct 4527 ms 30380 KB Output is correct
8 Correct 4729 ms 30308 KB Output is correct
9 Correct 5627 ms 30648 KB Output is correct
10 Correct 1067 ms 30260 KB Output is correct
11 Correct 4577 ms 30408 KB Output is correct
12 Correct 16 ms 12292 KB Output is correct
13 Correct 5022 ms 115516 KB Output is correct
14 Execution timed out 8083 ms 117368 KB Time limit exceeded
15 Halted 0 ms 0 KB -