Submission #387529

#	Time	Username	Problem	Language	Result	Execution time	Memory
387529		aryan12	Factories (JOI14_factories)	C++17	0 / 100	43 ms	32620 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const long long MAXN = 5e5 + 5;
vector<pair<long long, long long> > g[MAXN];
long long Subtree[MAXN], lastCnt[MAXN], centroidParent[MAXN];
long long distFromRoot[MAXN], ans[MAXN];
bool isTaken[MAXN];
long long DP[20][MAXN], depth[MAXN];
long long cnt = 0;

void FindDist(long long node, long long par) {
    DP[0][node] = par;
    for(long long i = 0; i < g[node].size(); i++) {
        if(g[node][i].first != par) {
            distFromRoot[g[node][i].first] = distFromRoot[node] + g[node][i].second;
            depth[g[node][i].first] = depth[node] + 1;
            FindDist(g[node][i].first, node);
        }
    }
}

long long SubtreeDfs(long long node, long long par) {
    Subtree[node] = 1;
    for(long long i = 0; i < g[node].size(); i++) {
        if(!isTaken[g[node][i].first] && !isTaken[node] && g[node][i].first != par) {
            Subtree[node] += SubtreeDfs(g[node][i].first, node);
        }
    }
    return Subtree[node];
}

long long FindCentroid(long long node, long long par, long long totalSize) {
    for(long long i = 0; i < g[node].size(); i++) {
        if(!isTaken[g[node][i].first] && !isTaken[node] && g[node][i].first != par) {
            if(Subtree[g[node][i].first] > totalSize / 2) {
                return FindCentroid(g[node][i].first, node, totalSize);
            }
        }
    }
    return node;
}

void BuildCentroid(long long centroid, long long par) {
    long long siz = SubtreeDfs(centroid, -1);
    centroid = FindCentroid(centroid, par, siz);
    isTaken[centroid] = true;
    if(par == -1)
        centroidParent[centroid] = centroid;
    else
        centroidParent[centroid] = par;
    for(long long i = 0; i < g[centroid].size(); i++) {
        if(!isTaken[g[centroid][i].first]) {
            BuildCentroid(g[centroid][i].first, centroid);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(long long i = 0; i < MAXN; i++) {
        isTaken[i] = false;
        Subtree[i] = 0;
        distFromRoot[i] = 0;
        centroidParent[i] = i;
        lastCnt[i] = 0;
        ans[i] = 1e15;
    }
    cnt = 0;
    for(long long i = 0; i < N - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    distFromRoot[0] = 0;
    depth[0] = 0;
    FindDist(0, -1);
    BuildCentroid(0, -1);
    for(long long i = 1; i < 20; i++) {
        for(long long j = 0; j < N; j++) {
            if(DP[i - 1][j] == -1) {
                DP[i][j] = -1;
            }
            else {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
        }
    }
    /*cout << "Centroid Parents\n";
    for(long long i = 0; i < N; i++) {
        cout << centroidParent[i] << " ";
    }
    cout << "\n";
    cout << "distFromRoot\n";
    for(long long i = 0; i < N; i++) {
        cout << distFromRoot[i] << " ";
    }
    cout << "\n";
    cout << "Normal parents\n";
    for(long long i = 0; i < N; i++) {
        cout << DP[0][i] << " ";
    }
    cout << "\n";
    cout << "Binary lifting array\n";
    for(long long i = 0; i < 20; i++) {
        for(long long j = 0; j < N; j++) {
            cout << DP[i][j] << " ";
        }
        cout << "\n";
    }*/
}

long long LCA(long long x, long long y) {
    if(depth[x] < depth[y])
        swap(x, y);
    long long diff = depth[x] - depth[y];
    /*cout << "IN LCA\n";
    cout << "x = " << x << ", y = " << y << ", diff = " << diff << "\n";
    cout << "(1 << 2) = " << (1 << 2) << "\n";*/
    for(long long i = 19; i >= 0; i--) {
        if(diff >= (1 << i)) {
            diff -= (1 << i);
            x = DP[i][x];
        }
    }
    //cout << "x = " << x << ", y = " << y << "\n";
    if(x == y) {
        //cout << "Answer = " << x << "\n";
        return x;
    }
    for(long long i = 19; i >= 0; i--) {
        if(DP[i][x] != DP[i][y]) {
            x = DP[i][x];
            y = DP[i][y];
        }
    }
    //cout << "Answer = " << DP[0][x] << "\n";
    return DP[0][x];
}

void Update(long long node) {
    ans[node] = 0;
    lastCnt[node] = cnt;
    long long initial = node;
    while(centroidParent[node] != node) {
        node = centroidParent[node];
        //cout << "Update function, updating " << initial << "\n";
        //cout << "initial = " << initial << ", node = " << node << ", distance = " << distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] << "\n";
        if(lastCnt[node] != cnt) {
            ans[node] = distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)];
            lastCnt[node] = cnt;
        }
        else {
            ans[node] = min(ans[node], distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)]);
        }
        //cout << "ans[node] = " << ans[node] << "\n";
    }
}

long long Query2(long long node) {
    if(lastCnt[node] == cnt)
        return 0;
    long long initial = node;
    long long res = 1e15;
    while(centroidParent[node] != node) {
        node = centroidParent[node];
        //cout << "Query function, querying " << initial << "\n";
        //cout << "LCA(initial, node) = " << LCA(initial, node) << "\n";
        //cout << "initial = " << initial << ", node = " << node << ", distance = " << distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] << "\n";
        if(lastCnt[node] == cnt) {
            res = min(res, distFromRoot[node] + distFromRoot[initial] - 2 * distFromRoot[LCA(initial, node)] + ans[node]);
        }
        //cout << "res = " << res << "\n";
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    cnt++;
    for(long long i = 0; i < S; i++) {
        Update(X[i]);
    }
    /*cout << "Outputting ans array\n";
    for(long long i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
    cout << "Outputting lastCnt array\n";
    for(long long i = 0; i < N; i++) {
        cout << lastCnt[i] << " ";
    }
    cout << "\n";*/
    long long res = 1e15;
    for(long long i = 0; i < T; i++) {
        res = min(res, Query2(Y[i]));
    }
    return res;
}

Compilation message (stderr)

factories.cpp: In function 'void FindDist(long long int, long long int)':
factories.cpp:15:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int SubtreeDfs(long long int, long long int)':
factories.cpp:26:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int FindCentroid(long long int, long long int, long long int)':
factories.cpp:35:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void BuildCentroid(long long int, long long int)':
factories.cpp:53:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(long long i = 0; i < g[centroid].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~

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