제출 #1169316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169316		chikien2009	Factories (JOI14_factories)	C++20	33 / 100	8092 ms	121184 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

// void setup()
// {
// #ifndef ONLINE_JUDGE
//     freopen("test.inp", "r", stdin);
//     freopen("test.out", "w", stdout);
// #endif
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
// }

int sz[500000], last_centroid[500000], depth[500000], pre[20][500000];
long long dist[500000], nearest[500000], temp;
bool check[500000];
vector<pair<int, int>> g[500000];

void CalculateSize(int node, int par)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i.first != par && !check[i.first])
        {
            CalculateSize(i.first, node);
            sz[node] += sz[i.first];
        }
    }
}

int GetCentroid(int node, int par, int root)
{
    for (auto &i : g[node])
    {
        if (i.first != par && !check[i.first] && sz[i.first] * 2 > sz[root])
        {
            return GetCentroid(i.first, node, root);
        }
    }
    return node;
}

void FindCentroid(int node, int LastCentroid)
{
    int centroid;
    CalculateSize(node, node);
    centroid = GetCentroid(node, node, node);
    last_centroid[centroid] = LastCentroid;
    check[centroid] = true;
    for (auto &i : g[centroid])
    {
        if (!check[i.first])
        {
            FindCentroid(i.first, centroid);
        }
    }
}

void FormLCA(int node, int par)
{
    pre[0][node] = par;
    for (int i = 1; i < 20; ++i)
    {
        pre[i][node] = pre[i - 1][pre[i - 1][node]];
    }
    for (auto &i : g[node])
    {
        if (i.first != par)
        {
            depth[i.first] = depth[node] + 1;
            dist[i.first] = dist[node] + i.second;
            FormLCA(i.first, node);
        }
    }
}

int LCA(int ina, int inb)
{
    if (depth[ina] != depth[inb])
    {
        if (depth[ina] < depth[inb])
        {
            swap(ina, inb);
        }
        for (int i = 19; i >= 0; --i)
        {
            if (depth[pre[i][ina]] >= depth[inb])
            {
                ina = pre[i][ina];
            }
        }
    }
    if (ina == inb)
    {
        return ina;
    }
    for (int i = 19; i >= 0; --i)
    {
        if (pre[i][ina] != pre[i][inb])
        {
            ina = pre[i][ina];
            inb = pre[i][inb];
        }
    }
    return pre[0][ina];
}

long long Dist(int ina, int inb)
{
    return dist[ina] + dist[inb] - 2 * dist[LCA(ina, inb)];
}

void Update(int node)
{
    int cur = node;
    while (cur != -1)
    {
        temp = Dist(cur, node);
        nearest[cur] = (nearest[cur] == -1 ? temp : min(temp, nearest[cur]));
        cur = last_centroid[cur];
    }
}

void Reset(int node)
{
    int cur = node;
    while (cur != -1)
    {
        nearest[cur] = -1;
        cur = last_centroid[cur];
    }
}

long long Get(int node)
{
    long long res = -1;
    int cur = node;
    while (cur != -1)
    {
        if (nearest[cur] != -1)
        {
            temp = Dist(cur, node) + nearest[cur];
            res = (res == -1 ? temp : min(temp, res));
        }
        cur = last_centroid[cur];
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[])
{
    long long res = 1e18;
    for (int i = 0; i < S; ++i)
    {
        Update(X[i]);
    }
    for (int i = 0; i < T; ++i)
    {
        res = min(res, Get(Y[i]));
    }
    for (int i = 0; i < S; ++i)
    {
        Reset(X[i]);
    }
    return res;
}

void Init(int N, int A[], int B[], int D[])
{
    fill_n(nearest, N, -1);
    for (int i = 0; i < N - 1; ++i)
    {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    depth[0] = dist[0] = 0;
    FindCentroid(0, -1);
    FormLCA(0, 0);
}

// int main()
// {
//     setup();

//     int n, q, s, t;
//     cin >> n >> q;
//     int A[n], B[n], D[n];
//     for (int i = 0; i < n - 1; ++i)
//     {
//         cin >> A[i] >> B[i] >> D[i];
//     }
//     Init(n, A, B, D);
//     while (q--)
//     {
//         cin >> s >> t;
//         for (int i = 0; i < s; ++i)
//         {
//             cin >> A[i];
//         }
//         for (int i = 0; i < t; ++i)
//         {
//             cin >> B[i];
//         }
//         cout << Query(s, A, t, B) << "\n";
//     }
//     return 0;
// }

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67