oj.uz

Submission #516481

# Submission time Handle Problem Language Result Execution time Memory
516481 2022-01-21T11:55:57 Z Jomnoi Factories (JOI14_factories) C++17
15 / 100
 8000 ms 99688 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;
    }
    updated.clear();
    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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12428 KB Output is correct
2 Correct 3109 ms 20896 KB Output is correct
3 Correct 4664 ms 21244 KB Output is correct
4 Correct 4528 ms 21476 KB Output is correct
5 Correct 5608 ms 21636 KB Output is correct
6 Correct 1040 ms 21084 KB Output is correct
7 Correct 4551 ms 21084 KB Output is correct
8 Correct 4758 ms 21288 KB Output is correct
9 Correct 5624 ms 21636 KB Output is correct
10 Correct 1048 ms 21084 KB Output is correct
11 Correct 4541 ms 21112 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 5102 ms 96940 KB Output is correct
3 Execution timed out 8071 ms 99688 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12428 KB Output is correct
2 Correct 3109 ms 20896 KB Output is correct
3 Correct 4664 ms 21244 KB Output is correct
4 Correct 4528 ms 21476 KB Output is correct
5 Correct 5608 ms 21636 KB Output is correct
6 Correct 1040 ms 21084 KB Output is correct
7 Correct 4551 ms 21084 KB Output is correct
8 Correct 4758 ms 21288 KB Output is correct
9 Correct 5624 ms 21636 KB Output is correct
10 Correct 1048 ms 21084 KB Output is correct
11 Correct 4541 ms 21112 KB Output is correct
12 Correct 14 ms 12280 KB Output is correct
13 Correct 5102 ms 96940 KB Output is correct
14 Execution timed out 8071 ms 99688 KB Time limit exceeded
15 Halted 0 ms 0 KB -