oj.uz

Submission #347208

# Submission time Handle Problem Language Result Execution time Memory
347208 2021-01-12T11:18:21 Z dolphingarlic Factories (JOI14_factories) C++14
15 / 100
 8000 ms 169408 KB 
#include "factories.h"

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

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] / 2);
    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 = 0x3f3f3f3f3f3f3f3f;
    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] = 0x3f3f3f3f3f3f3f3f;
            curr = c_par[curr];
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16620 KB Output is correct
2 Correct 1834 ms 27756 KB Output is correct
3 Correct 2918 ms 27808 KB Output is correct
4 Correct 2880 ms 27796 KB Output is correct
5 Correct 3880 ms 28076 KB Output is correct
6 Correct 635 ms 27756 KB Output is correct
7 Correct 2778 ms 27812 KB Output is correct
8 Correct 2881 ms 28020 KB Output is correct
9 Correct 3751 ms 28396 KB Output is correct
10 Correct 629 ms 27756 KB Output is correct
11 Correct 2659 ms 28012 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 4958 ms 167428 KB Output is correct
3 Execution timed out 8093 ms 169408 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16620 KB Output is correct
2 Correct 1834 ms 27756 KB Output is correct
3 Correct 2918 ms 27808 KB Output is correct
4 Correct 2880 ms 27796 KB Output is correct
5 Correct 3880 ms 28076 KB Output is correct
6 Correct 635 ms 27756 KB Output is correct
7 Correct 2778 ms 27812 KB Output is correct
8 Correct 2881 ms 28020 KB Output is correct
9 Correct 3751 ms 28396 KB Output is correct
10 Correct 629 ms 27756 KB Output is correct
11 Correct 2659 ms 28012 KB Output is correct
12 Correct 15 ms 16364 KB Output is correct
13 Correct 4958 ms 167428 KB Output is correct
14 Execution timed out 8093 ms 169408 KB Time limit exceeded
15 Halted 0 ms 0 KB -