Submission #488108

#	Time	Username	Problem	Language	Result	Execution time	Memory
488108		macktvz	Factories (JOI14_factories)	C++17	0 / 100	8 ms	3152 KiB

factories

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

// keep track of min distance from query i 0 node to ancestor and
// min distance form query i 1 node to ancestor

// for each query, for each node, for each ancestor of node record min distance for this ancestor for this query
// for second list, do same while keeping track of min distance found so far
const int Ni = 1e5+1;
const int S = 17;
vector<pair<int,int>> adj[Ni];
int sz[Ni];
int up[Ni][S];
int dep[Ni];
long long dist[Ni];
bool cen[Ni];
int cp[Ni];
int n;
long long mins[Ni];


void dsz(int u, int p) {
    sz[u] = 1;
    for(pair<int,int> i : adj[u]) {
        if (i.first != p && !cen[i.first]) {
            dsz(i.first,u);
            sz[u] += sz[i.first];
        }
    }
}

void dfsa(int u, int p) {
    for(int i = 1; i < S; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    for(pair<int,int> i : adj[u]) {
        if (i.first != p) {
            dist[i.first] = dist[u]+i.second; 
            dep[i.first] = dep[up[i.first][0] = u] + 1;
            dfsa(i.first,u);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x,y);
    x = up[x][dep[x]-dep[y]];
    if (x == y) return x;
    for(int i = 0; i < S; i++) {
        if (up[x][i] != up[x][i]) {
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

long long d(int x, int y) {
    return dist[x]+dist[y]-2*dist[lca(x,y)];
}

int find(int u, int p,int n) {
    for(pair<int,int> i : adj[u]) {
        if (i.first != p && !cen[i.first]) {
            if (sz[i.first]*2 > n) return find(i.first,u,n);
        }
    }
    return u;
}

void build(int u, int centr) {
    dsz(u,centr);
    int cent = find(u,centr,sz[u]);
    cp[cent] = centr;
    cen[cent] = true;
    for(pair<int,int> i : adj[cent]) {
        if (!cen[i.first]) build(i.first,cent);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N-1; i++) {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
        mins[i] = -1;
    }
    mins[N-1] = -1;
    n = N;
    dep[0] = 0;
    dist[0] = 0;
    up[0][0] = 0;
    dfsa(0,-1);
    build(0,-1);
}



long long Query(int S, int X[], int T, int Y[]) {
    vector<int> vis;
    for(int i = 0; i < S; i++) {
        vis.push_back(X[i]);
        mins[X[i]] = 0;
        int curr = cp[X[i]];
        while (curr != -1) {
            vis.push_back(curr);
            long long dis = d(X[i],curr);
            if (mins[curr] == -1) mins[curr] = dis;
            else mins[curr] = min(mins[curr],dis);
            curr = cp[curr];
        }
    }
    long long ret = 9223372036854775807;
    for(int i = 0; i < T; i++) {
        if (mins[Y[i]] != -1) ret = min(ret,mins[Y[i]]);
        int curr = cp[Y[i]];
        while(curr != -1) {
            if (mins[curr] != -1) ret = min(ret,mins[curr] + d(Y[i],curr));
            curr = cp[curr];
        }
    }
    for(int i : vis) mins[i] = -1;
    return ret;
}

Compilation message (stderr)

factories.cpp: In function 'int lca(int, int)':
factories.cpp:50:22: warning: self-comparison always evaluates to false [-Wtautological-compare]
   50 |         if (up[x][i] != up[x][i]) {
      |             ~~~~~~~~ ^~ ~~~~~~~~

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