oj.uz

Submission #516480

# Submission time Handle Problem Language Result Execution time Memory
516480 2022-01-21T11:55:10 Z Jomnoi Factories (JOI14_factories) C++17
0 / 100
 8000 ms 97600 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];
vector <int> updated;

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 update(const int &u) {
    int a = u;
    while(a != -1) {
        updated.push_back(a);
        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 res = INF;
    for(int i = 0; i < T; i++) {
        res = min(res, query(Y[i] + 1));
    }

    for(auto v : updated) {
        ans[v] = INF;
    }
    return res;
}

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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 13664 KB Output is correct
2 Execution timed out 8086 ms 54024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12364 KB Output is correct
2 Execution timed out 8010 ms 97600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 13664 KB Output is correct
2 Execution timed out 8086 ms 54024 KB Time limit exceeded
3 Halted 0 ms 0 KB -