oj.uz

Submission #347265

# Submission time Handle Problem Language Result Execution time Memory
347265 2021-01-12T13:05:31 Z dolphingarlic Factories (JOI14_factories) C++14
15 / 100
 8000 ms 169492 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 (!processed[i.first] && i.first != parent) {
        get_subtree_sizes(i.first, node);
        subtree[node] += subtree[i.first];
    }
}

int get_centroid(int node, int parent, int tree_size) {
    bool searching = true;
    while (searching) {
        searching = false;
        for (pair<int, int> i : graph[node])
            if (!processed[i.first] && i.first != parent && subtree[i.first] > tree_size) {
                searching = true;
                parent = node;
                node = i.first;
                break;
            }
    }
    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 = 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 45 ms 16492 KB Output is correct
2 Correct 1722 ms 34996 KB Output is correct
3 Correct 2739 ms 35180 KB Output is correct
4 Correct 2763 ms 35436 KB Output is correct
5 Correct 3730 ms 35224 KB Output is correct
6 Correct 673 ms 35052 KB Output is correct
7 Correct 2665 ms 35308 KB Output is correct
8 Correct 2855 ms 35232 KB Output is correct
9 Correct 3754 ms 35296 KB Output is correct
10 Correct 620 ms 34924 KB Output is correct
11 Correct 2712 ms 35068 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16236 KB Output is correct
2 Correct 4957 ms 167816 KB Output is correct
3 Execution timed out 8100 ms 169492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16492 KB Output is correct
2 Correct 1722 ms 34996 KB Output is correct
3 Correct 2739 ms 35180 KB Output is correct
4 Correct 2763 ms 35436 KB Output is correct
5 Correct 3730 ms 35224 KB Output is correct
6 Correct 673 ms 35052 KB Output is correct
7 Correct 2665 ms 35308 KB Output is correct
8 Correct 2855 ms 35232 KB Output is correct
9 Correct 3754 ms 35296 KB Output is correct
10 Correct 620 ms 34924 KB Output is correct
11 Correct 2712 ms 35068 KB Output is correct
12 Correct 15 ms 16236 KB Output is correct
13 Correct 4957 ms 167816 KB Output is correct
14 Execution timed out 8100 ms 169492 KB Time limit exceeded
15 Halted 0 ms 0 KB -