Submission #1169352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169352		chikien2009	Factories (JOI14_factories)	C++20	100 / 100	2508 ms	158156 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 ind, x, y, sz[500000], last_centroid[500000], depth[500000], sp[20][1000000], head[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)
{
    head[node] = ind;
    sp[0][ind] = node;
    ind++;
    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);
            sp[0][ind] = node;
            ind++;
        }
    }
}

int LCA(int ina, int inb)
{
    int k;
    ina = head[ina];
    inb = head[inb];
    if (ina > inb)
    {
        swap(ina, inb);
    }
    k = __lg(inb - ina + 1);
    ina = sp[k][ina];
    inb = sp[k][inb - (1 << k) + 1];
    return (depth[ina] < depth[inb] ? ina : inb);
}

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] = ind = 0;
    FindCentroid(0, -1);
    FormLCA(0, 0);
    for (int i = 1; i < 20; ++i)
    {
        for (int j = 0; j + (1 << i) <= ind; ++j)
        {
            x = sp[i - 1][j];
            y = sp[i - 1][j + (1 << (i - 1))];
            sp[i][j] = (depth[x] < depth[y] ? x : y);
        }
    }
}

// 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: 67 / 67