oj.uz

Submission #348496

# Submission time Handle Problem Language Result Execution time Memory
348496 2021-01-15T05:22:14 Z dolphingarlic Factories (JOI14_factories) C++14
100 / 100
 7389 ms 256260 KB 
#include "factories.h"

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

const ll INF = 1e18;

vector<pair<int, ll>> graph[500000], vtree[500000];
int tin[500000], tout[500000], timer = 0, anc[500000][19];
ll to_anc[500000][19], to_X[500000], to_Y[500000];

void lca_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;
        lca_dfs(i.first, node);
    }
    tout[node] = timer++;
}

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

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    for (int i = 18; ~i; i--) if (!is_ancestor(anc[u][i], v)) u = anc[u][i];
    return anc[u][0];
}

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 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]});
    }
    lca_dfs();
    memset(to_X, 0x3f, sizeof to_X); memset(to_Y, 0x3f, sizeof to_Y);
}

bool cmp(int u, int v) { return tin[u] < tin[v]; }

ll ans;

void dfs1(int node, int parent = 0) {
    for (pair<int, ll> i : vtree[node]) if (i.first != parent) {
        dfs1(i.first, node);
        to_X[node] = min(to_X[node], to_X[i.first] + i.second);
        to_Y[node] = min(to_Y[node], to_Y[i.first] + i.second);
    }
}

void dfs2(int node, int parent = 0, ll par_to_X = INF, ll par_to_Y = INF) {
    to_X[node] = min(to_X[node], par_to_X);
    to_Y[node] = min(to_Y[node], par_to_Y);
    ans = min(ans, to_X[node] + to_Y[node]);
    for (pair<int, ll> i : vtree[node]) if (i.first != parent) {
        ll nxt_par_to_X = i.second + min(par_to_X, to_X[node]);
        ll nxt_par_to_Y = i.second + min(par_to_Y, to_Y[node]);
        dfs2(i.first, node, nxt_par_to_X, nxt_par_to_Y);
    }
}

ll Query(int S, int X[], int T, int Y[]) {
    vector<int> nodes;
    for (int i = 0; i < S; i++) {
        to_X[X[i]] = 0;
        nodes.push_back(X[i]);
    }
    for (int i = 0; i < T; i++) {
        to_Y[Y[i]] = 0;
        nodes.push_back(Y[i]);
    }
    sort(nodes.begin(), nodes.end(), cmp);
    for (int i = 1; i < S + T; i++) nodes.push_back(lca(nodes[i - 1], nodes[i]));
    sort(nodes.begin(), nodes.end(), cmp);
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    vector<int> stck;
    for (int i : nodes) {
        while (stck.size() > 1 && !is_ancestor(stck.back(), i)) {
            int u = stck[stck.size() - 2], v = stck.back();
            vtree[u].push_back({v, dist(u, v)});
            stck.pop_back();
        }
        stck.push_back(i);
    }
    while (stck.size() > 1) {
        int u = stck[stck.size() - 2], v = stck.back();
        vtree[u].push_back({v, dist(u, v)});
        stck.pop_back();
    }
    ans = LLONG_MAX;
    dfs1(stck[0]);
    dfs2(stck[0]);
    for (int i : nodes) {
        to_X[i] = to_Y[i] = INF;
        vtree[i].clear();
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32108 KB Output is correct
2 Correct 1467 ms 41452 KB Output is correct
3 Correct 1515 ms 50796 KB Output is correct
4 Correct 1477 ms 50924 KB Output is correct
5 Correct 1237 ms 51308 KB Output is correct
6 Correct 1052 ms 50796 KB Output is correct
7 Correct 1478 ms 51028 KB Output is correct
8 Correct 1450 ms 50948 KB Output is correct
9 Correct 1229 ms 51280 KB Output is correct
10 Correct 1058 ms 50796 KB Output is correct
11 Correct 1474 ms 50796 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31980 KB Output is correct
2 Correct 2133 ms 185708 KB Output is correct
3 Correct 4218 ms 191300 KB Output is correct
4 Correct 1550 ms 183368 KB Output is correct
5 Correct 3625 ms 231412 KB Output is correct
6 Correct 4376 ms 211036 KB Output is correct
7 Correct 3745 ms 85892 KB Output is correct
8 Correct 1618 ms 85212 KB Output is correct
9 Correct 2995 ms 92924 KB Output is correct
10 Correct 3678 ms 87036 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32108 KB Output is correct
2 Correct 1467 ms 41452 KB Output is correct
3 Correct 1515 ms 50796 KB Output is correct
4 Correct 1477 ms 50924 KB Output is correct
5 Correct 1237 ms 51308 KB Output is correct
6 Correct 1052 ms 50796 KB Output is correct
7 Correct 1478 ms 51028 KB Output is correct
8 Correct 1450 ms 50948 KB Output is correct
9 Correct 1229 ms 51280 KB Output is correct
10 Correct 1058 ms 50796 KB Output is correct
11 Correct 1474 ms 50796 KB Output is correct
12 Correct 23 ms 31980 KB Output is correct
13 Correct 2133 ms 185708 KB Output is correct
14 Correct 4218 ms 191300 KB Output is correct
15 Correct 1550 ms 183368 KB Output is correct
16 Correct 3625 ms 231412 KB Output is correct
17 Correct 4376 ms 211036 KB Output is correct
18 Correct 3745 ms 85892 KB Output is correct
19 Correct 1618 ms 85212 KB Output is correct
20 Correct 2995 ms 92924 KB Output is correct
21 Correct 3678 ms 87036 KB Output is correct
22 Correct 4774 ms 220968 KB Output is correct
23 Correct 4344 ms 221972 KB Output is correct
24 Correct 5738 ms 226288 KB Output is correct
25 Correct 5663 ms 228760 KB Output is correct
26 Correct 7048 ms 219352 KB Output is correct
27 Correct 5106 ms 256260 KB Output is correct
28 Correct 2768 ms 216700 KB Output is correct
29 Correct 7302 ms 217816 KB Output is correct
30 Correct 7366 ms 217028 KB Output is correct
31 Correct 7389 ms 218112 KB Output is correct
32 Correct 2891 ms 95560 KB Output is correct
33 Correct 1950 ms 88412 KB Output is correct
34 Correct 3088 ms 84332 KB Output is correct
35 Correct 2921 ms 84076 KB Output is correct
36 Correct 3736 ms 85100 KB Output is correct
37 Correct 3759 ms 85256 KB Output is correct