제출 #720301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720301		thimote75	공장들 (JOI14_factories)	C++14	100 / 100	5616 ms	245496 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67