Submission #483269

#	Time	Username	Problem	Language	Result	Execution time	Memory
483269		Alexandruabcde	Factories (JOI14_factories)	C++14	100 / 100	5150 ms	364372 KiB

factories

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

using namespace std;

constexpr int NMAX = 5e5 + 5;
typedef long long LL;
typedef pair <int, LL> PIL;

vector <PIL> G[NMAX];
vector <PIL> Root[NMAX];

bool viz[NMAX];
int Size[NMAX];

LL Dist[NMAX];

void Initial_Dfs (int Node, int dad = -1) {
    Size[Node] = 1;

    for (auto it : G[Node]) {
        int to = it.first;
        if (to == dad || viz[to]) continue;

        Initial_Dfs(to, Node);
        Size[Node] += Size[to];
    }
}

int GetCentroid (int Node, int Sz, int dad = -1) {
    int Max = Sz - Size[Node];
    for (auto it : G[Node]) {
        int to = it.first;
        if (to == dad || viz[to]) continue;

        int x = GetCentroid(to, Sz, Node);

        if (x != 0) return x;

        Max = max(Max, Size[to]);
    }

    if (Max <= (Sz + 1) / 2) return Node;

    return 0;
}

void Add (int Node, int cent, LL dist, int dad = -1) {
    Root[Node].push_back({cent, dist});

    for (auto it : G[Node]) {
        int to = it.first;

        if (to == dad || viz[to]) continue;

        Add(to, cent, dist + it.second, Node);
    }
}

void CentroidDecomposition (int Node) {
    Initial_Dfs(Node);

    int centroid = GetCentroid(Node, Size[Node]);
    Add(centroid, centroid, 0);

    viz[centroid] = 1;

    for (auto it : G[centroid]) {
        int to = it.first;

        if (!viz[to]) CentroidDecomposition(to);
    }
}

void Init (int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++ i ) {
        ++ A[i];
        ++ B[i];
        G[A[i]].push_back({B[i], D[i]});
        G[B[i]].push_back({A[i], D[i]});
    }

    CentroidDecomposition(1);

    for (int i = 1; i <= N; ++ i )
        Dist[i] = -1;
}

void Compute (int Node) {
    for (auto it : Root[Node]) {
        if (Dist[it.first] == -1) Dist[it.first] = it.second;

        Dist[it.first] = min(Dist[it.first], it.second);
    }
}

LL Minimum (int Node) {
    LL ans = 1000000000000000;
    for (auto it : Root[Node]) {
        if (Dist[it.first] == -1) continue;

        ans = min(ans, Dist[it.first] + it.second);
    }

    return ans;
}

void Delete (int Node) {
    for (auto it : Root[Node])
        Dist[it.first] = -1;
}

long long Query (int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++ i )
        Compute(X[i]+1);

    LL ans = 1000000000000000;

    for (int i = 0; i < T; ++ i )
        ans = min(ans, Minimum(Y[i]+1));

    for (int i = 0; i < S; ++ i )
        Delete(X[i] + 1);

    return ans;
}

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