oj.uz

Submission #347267

# Submission time Handle Problem Language Result Execution time Memory
347267 2021-01-12T13:08:09 Z dolphingarlic Factories (JOI14_factories) C++14
15 / 100
 8000 ms 169248 KB 
#include "factories.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

vector<pair<int, int>> graph[500000];
int tin[500000], tout[500000], timer = 0, anc[500000][19];
ll to_anc[500000][19];
bool processed[500000];
int subtree[500000], c_par[500000];
ll c_dist[500000];

void dfs(int node = 0, int parent = -1) {
    tin[node] = timer++;
    for (int i = 1; i < 19; i++) {
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
        to_anc[node][i] = to_anc[node][i - 1] + to_anc[anc[node][i - 1]][i - 1];
    }
    for (pair<int, int> i : graph[node]) if (i.first != parent) {
        anc[i.first][0] = node;
        to_anc[i.first][0] = i.second;
        dfs(i.first, node);
    }
    tout[node] = timer++;
}

inline bool is_ancestor(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }

ll dist(int u, int v) {
    ll ans = 0;
    for (int i = 18; ~i; i--) if (!is_ancestor(anc[u][i], v)) {
        ans += to_anc[u][i];
        u = anc[u][i];
    }
    if (!is_ancestor(u, v)) ans += to_anc[u][0];
    for (int i = 18; ~i; i--) if (!is_ancestor(anc[v][i], u)) {
        ans += to_anc[v][i];
        v = anc[v][i];
    }
    if (!is_ancestor(v, u)) ans += to_anc[v][0];
    return ans; 
}

void get_subtree_sizes(int node, int parent = -1) {
    subtree[node] = 1;
    for (pair<int, int> i : graph[node]) if (i.first != parent && !processed[i.first]) {
        get_subtree_sizes(i.first, node);
        subtree[node] += subtree[i.first];
    }
}

int get_centroid(int node, int parent, int tree_size) {
    for (pair<int, int> i : graph[node])
        if (i.first != parent && !processed[i.first] && subtree[i.first] > tree_size)
            return get_centroid(i.first, node, tree_size);
    return node;
}

void centroid_decomp(int node = 0, int prv_centroid = -1) {
    get_subtree_sizes(node);
    int centroid = get_centroid(node, -1, subtree[node] >> 1);
    c_par[centroid] = prv_centroid;
    processed[centroid] = true;
    for (pair<int, int> i : graph[centroid]) if (!processed[i.first])
        centroid_decomp(i.first, centroid);
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        graph[A[i]].push_back({B[i], D[i]});
        graph[B[i]].push_back({A[i], D[i]});
    }
    dfs();
    centroid_decomp();
    memset(c_dist, 0x3f, sizeof c_dist);
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int curr = X[i];
        while (curr != -1) {
            c_dist[curr] = min(c_dist[curr], dist(X[i], curr));
            curr = c_par[curr];
        }
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        int curr = Y[i];
        while (curr != -1) {
            ans = min(ans, c_dist[curr] + dist(Y[i], curr));
            curr = c_par[curr];
        }
    }
    for (int i = 0; i < S; i++) {
        int curr = X[i];
        while (curr != -1) {
            c_dist[curr] = INF;
            curr = c_par[curr];
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16492 KB Output is correct
2 Correct 1677 ms 25588 KB Output is correct
3 Correct 2802 ms 25608 KB Output is correct
4 Correct 2714 ms 25836 KB Output is correct
5 Correct 3675 ms 26024 KB Output is correct
6 Correct 624 ms 25580 KB Output is correct
7 Correct 2667 ms 25708 KB Output is correct
8 Correct 2819 ms 25816 KB Output is correct
9 Correct 3698 ms 25900 KB Output is correct
10 Correct 665 ms 25452 KB Output is correct
11 Correct 2667 ms 25816 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16364 KB Output is correct
2 Correct 4972 ms 167552 KB Output is correct
3 Execution timed out 8086 ms 169248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16492 KB Output is correct
2 Correct 1677 ms 25588 KB Output is correct
3 Correct 2802 ms 25608 KB Output is correct
4 Correct 2714 ms 25836 KB Output is correct
5 Correct 3675 ms 26024 KB Output is correct
6 Correct 624 ms 25580 KB Output is correct
7 Correct 2667 ms 25708 KB Output is correct
8 Correct 2819 ms 25816 KB Output is correct
9 Correct 3698 ms 25900 KB Output is correct
10 Correct 665 ms 25452 KB Output is correct
11 Correct 2667 ms 25816 KB Output is correct
12 Correct 15 ms 16364 KB Output is correct
13 Correct 4972 ms 167552 KB Output is correct
14 Execution timed out 8086 ms 169248 KB Time limit exceeded
15 Halted 0 ms 0 KB -