oj.uz

Submission #347171

# Submission time Handle Problem Language Result Execution time Memory
347171 2021-01-12T07:31:37 Z dolphingarlic Factories (JOI14_factories) C++14
15 / 100
 8000 ms 248920 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][20];
ll to_anc[500000][20];
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 < 20; 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++;
}

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 = 19; ~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 = 19; ~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();
    for (int i = 0; i < N; i++) c_dist[i] = LLONG_MAX / 2;
}

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 24556 KB Output is correct
2 Correct 1790 ms 43500 KB Output is correct
3 Correct 2866 ms 43440 KB Output is correct
4 Correct 2849 ms 43500 KB Output is correct
5 Correct 3971 ms 43756 KB Output is correct
6 Correct 678 ms 43500 KB Output is correct
7 Correct 2838 ms 43516 KB Output is correct
8 Correct 2955 ms 43472 KB Output is correct
9 Correct 3986 ms 43672 KB Output is correct
10 Correct 691 ms 43456 KB Output is correct
11 Correct 2802 ms 43372 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24172 KB Output is correct
2 Correct 5415 ms 247116 KB Output is correct
3 Execution timed out 8121 ms 248920 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 24556 KB Output is correct
2 Correct 1790 ms 43500 KB Output is correct
3 Correct 2866 ms 43440 KB Output is correct
4 Correct 2849 ms 43500 KB Output is correct
5 Correct 3971 ms 43756 KB Output is correct
6 Correct 678 ms 43500 KB Output is correct
7 Correct 2838 ms 43516 KB Output is correct
8 Correct 2955 ms 43472 KB Output is correct
9 Correct 3986 ms 43672 KB Output is correct
10 Correct 691 ms 43456 KB Output is correct
11 Correct 2802 ms 43372 KB Output is correct
12 Correct 21 ms 24172 KB Output is correct
13 Correct 5415 ms 247116 KB Output is correct
14 Execution timed out 8121 ms 248920 KB Time limit exceeded
15 Halted 0 ms 0 KB -