oj.uz

Submission #347177

# Submission time Handle Problem Language Result Execution time Memory
347177 2021-01-12T07:39:19 Z dolphingarlic Factories (JOI14_factories) C++14
15 / 100
 8000 ms 224912 KB 
#include "factories.h"

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

set<pair<int, ll>> graph[500000];
int tin[500000], tout[500000], timer = 0, anc[500000][19];
ll to_anc[500000][19];
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, ll> 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, ll> i : graph[node]) if (i.first != parent) {
        get_subtree_sizes(i.first, node);
        subtree[node] += subtree[i.first];
    }
}

int get_centroid(int node, int parent, int tree_size) {
    for (pair<int, ll> i : graph[node])
        if (i.first != parent && 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;
    for (pair<int, ll> i : graph[centroid]) {
        graph[i.first].erase({centroid, i.second});
        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]].insert({B[i], D[i]});
        graph[B[i]].insert({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 50 ms 28268 KB Output is correct
2 Correct 1696 ms 37744 KB Output is correct
3 Correct 2787 ms 37868 KB Output is correct
4 Correct 2767 ms 37740 KB Output is correct
5 Correct 3786 ms 37984 KB Output is correct
6 Correct 650 ms 37612 KB Output is correct
7 Correct 2750 ms 37868 KB Output is correct
8 Correct 2862 ms 37868 KB Output is correct
9 Correct 3783 ms 38232 KB Output is correct
10 Correct 645 ms 37612 KB Output is correct
11 Correct 2716 ms 37740 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28012 KB Output is correct
2 Correct 5409 ms 222688 KB Output is correct
3 Execution timed out 8114 ms 224912 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28268 KB Output is correct
2 Correct 1696 ms 37744 KB Output is correct
3 Correct 2787 ms 37868 KB Output is correct
4 Correct 2767 ms 37740 KB Output is correct
5 Correct 3786 ms 37984 KB Output is correct
6 Correct 650 ms 37612 KB Output is correct
7 Correct 2750 ms 37868 KB Output is correct
8 Correct 2862 ms 37868 KB Output is correct
9 Correct 3783 ms 38232 KB Output is correct
10 Correct 645 ms 37612 KB Output is correct
11 Correct 2716 ms 37740 KB Output is correct
12 Correct 23 ms 28012 KB Output is correct
13 Correct 5409 ms 222688 KB Output is correct
14 Execution timed out 8114 ms 224912 KB Time limit exceeded
15 Halted 0 ms 0 KB -