oj.uz

Submission #720301

# Submission time Handle Problem Language Result Execution time Memory
720301 2023-04-07T22:05:55 Z thimote75 Factories (JOI14_factories) C++14
100 / 100
 5616 ms 245496 KB 
#include <bits/stdc++.h>
// #include "factories.h"

using namespace std;

#define num long long

#define t_road pair<int, num>
#define rnext first
#define rcost second
#define t_roads set<t_road>
#define graph vector<t_roads>

#define idata vector<int>
#define ndata vector<num>
#define ngrid vector<ndata>

#define inf 1e18

int nbNodes, nbQuery;
graph roads;

idata centroid_tree;
idata subtree_size;

ngrid centroid_tree_distances;

int subtree_dfs (int node, int parent) {
    subtree_size[node] = 1;

    for (t_road road : roads[node]) if (road.rnext != parent)
        subtree_size[node] += subtree_dfs(road.rnext, node);

    return subtree_size[node];
}
int centroid (int node, int parent, int compSize) {
    for (t_road road : roads[node]) 
        if (road.rnext != parent
         && subtree_size[road.rnext] > compSize)
            return centroid(road.rnext, node, compSize);
    
    return node;
}
void update_distances (int node, int parent, num distance) {
    centroid_tree_distances[node].push_back(distance);

    for (t_road road : roads[node]) if (road.rnext != parent)
        update_distances(road.rnext, node, distance + road.rcost);
}

void decompose (int node, int parent) {
    int c_size = subtree_dfs(node, -1);
    int centri = centroid(node, -1, c_size >> 1);

    update_distances(centri, -1, 0);

    centroid_tree[centri] = parent;

    while (roads[centri].size() != 0) {
        t_road road = *(roads[centri].begin());

        roads[centri].erase(road);
        roads[road.rnext].erase({ centri, road.rcost });

        decompose(road.rnext, centri);
    }
}

ndata query_metadata;

void enable (int start) {
    int id   = 0;
    int node = start;
    while (node != -1) {
        query_metadata[node] = min(
            query_metadata[node],
            centroid_tree_distances[start][id]
        );

        node = centroid_tree[node];

        id ++;
    }
}
void reset (int node) {
    while (node != -1) {
        query_metadata[node] = inf;
        node = centroid_tree[node];
    }
}
num query (int start) {
    num res = inf;
    int id   = 0;
    int node = start;
    while (node != -1) {
        res = min(
            res,
            query_metadata[node] + centroid_tree_distances[start][id]
        );

        node = centroid_tree[node];

        id ++;
    }
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    nbNodes = N;

    roads.resize(nbNodes);

    centroid_tree.resize(nbNodes);
    subtree_size .resize(nbNodes);

    centroid_tree_distances.resize(nbNodes);

    query_metadata.resize(nbNodes, inf);

    for (int iR = 0; iR + 1 < nbNodes; iR ++) {
        roads[A[iR]].insert({ B[iR], D[iR] });
        roads[B[iR]].insert({ A[iR], D[iR] });
    }
    decompose(0, -1);

    for (int i = 0; i < nbNodes; i ++)
        reverse(centroid_tree_distances[i].begin(), centroid_tree_distances[i].end());
}

num Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i ++) enable(X[i]);

    num res = inf;
    for (int i = 0; i < T; i ++)
        res = min(res, query(Y[i]));
    for (int i = 0; i < S; i ++) reset (X[i]);

    return res;
}

/*int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> nbNodes >> nbQuery;
    roads.resize(nbNodes);

    centroid_tree.resize(nbNodes);
    subtree_size .resize(nbNodes);

    centroid_tree_distances.resize(nbNodes);

    query_metadata.resize(nbNodes, inf);

    for (int iR = 1; iR < nbNodes; iR ++) {
        int a, b, c;
        cin >> a >> b >> c;

        roads[a].insert({ b, c });
        roads[b].insert({ a, c });
    }

    decompose(0, -1);

    for (int i = 0; i < nbNodes; i ++)
        reverse(centroid_tree_distances[i].begin(), centroid_tree_distances[i].end());
    
    for (int iQ = 0; iQ < nbQuery; iQ ++) {
        int s, t;
        cin >> s >> t;

        vector<int> S(s);
        for (int iS = 0; iS < s; iS ++) cin >> S[iS];

        for (int vS : S) enable(vS);
        
        num res = inf;
        for (int iT = 0; iT < t; iT ++) {
            int vT; cin >> vT;
        
            res = min(res, query(vT));
        }
        cout << res << endl;

        for (int vS : S) reset (vS);
    }
}*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 265 ms 19076 KB Output is correct
3 Correct 308 ms 19144 KB Output is correct
4 Correct 281 ms 19148 KB Output is correct
5 Correct 308 ms 19444 KB Output is correct
6 Correct 198 ms 18988 KB Output is correct
7 Correct 287 ms 19084 KB Output is correct
8 Correct 311 ms 19148 KB Output is correct
9 Correct 308 ms 19488 KB Output is correct
10 Correct 228 ms 19088 KB Output is correct
11 Correct 287 ms 19108 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2678 ms 162716 KB Output is correct
3 Correct 3973 ms 189052 KB Output is correct
4 Correct 1236 ms 152688 KB Output is correct
5 Correct 5163 ms 241420 KB Output is correct
6 Correct 3998 ms 191196 KB Output is correct
7 Correct 1020 ms 51960 KB Output is correct
8 Correct 410 ms 50116 KB Output is correct
9 Correct 1258 ms 59272 KB Output is correct
10 Correct 1033 ms 53540 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 265 ms 19076 KB Output is correct
3 Correct 308 ms 19144 KB Output is correct
4 Correct 281 ms 19148 KB Output is correct
5 Correct 308 ms 19444 KB Output is correct
6 Correct 198 ms 18988 KB Output is correct
7 Correct 287 ms 19084 KB Output is correct
8 Correct 311 ms 19148 KB Output is correct
9 Correct 308 ms 19488 KB Output is correct
10 Correct 228 ms 19088 KB Output is correct
11 Correct 287 ms 19108 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2678 ms 162716 KB Output is correct
14 Correct 3973 ms 189052 KB Output is correct
15 Correct 1236 ms 152688 KB Output is correct
16 Correct 5163 ms 241420 KB Output is correct
17 Correct 3998 ms 191196 KB Output is correct
18 Correct 1020 ms 51960 KB Output is correct
19 Correct 410 ms 50116 KB Output is correct
20 Correct 1258 ms 59272 KB Output is correct
21 Correct 1033 ms 53540 KB Output is correct
22 Correct 2837 ms 167964 KB Output is correct
23 Correct 3032 ms 173220 KB Output is correct
24 Correct 4476 ms 197244 KB Output is correct
25 Correct 4441 ms 201288 KB Output is correct
26 Correct 4323 ms 197820 KB Output is correct
27 Correct 5616 ms 245496 KB Output is correct
28 Correct 1363 ms 163032 KB Output is correct
29 Correct 4420 ms 197004 KB Output is correct
30 Correct 4302 ms 196720 KB Output is correct
31 Correct 4250 ms 197224 KB Output is correct
32 Correct 1381 ms 60312 KB Output is correct
33 Correct 452 ms 50360 KB Output is correct
34 Correct 781 ms 48160 KB Output is correct
35 Correct 802 ms 48644 KB Output is correct
36 Correct 1008 ms 50500 KB Output is correct
37 Correct 1029 ms 50452 KB Output is correct