Submission #488114

#	Time	Username	Problem	Language	Result	Execution time	Memory
488114		macktvz	Factories (JOI14_factories)	C++17	0 / 100	17 ms	3020 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 mnn[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 jump(int x, int d) {
    for(int i = 0; i < S; i++) {
        if ((d >> i) & 1) x = up[x][i];
    }
    return x;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x,y);
    x = jump(x,dep[x]-dep[y]);
    if (x == y) return x;
    for(int i = 0; i < S; i++) {
        if (up[x][i] != up[y][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;
                mnn[curr]=X[i];
            }
            else if (dis < mins[curr]){
                mins[curr] = dis;
                mnn[curr] = X[i];
            } 
            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,d(Y[i],mnn[curr]));
            curr = cp[curr];
        }
    }
    for(int i : vis) mins[i] = -1;
    return ret;
}

// int main() {
//     int x,y1;
//     cin >> x >> y1;
//     int A[x-1],B[x-1],D[x-1];
//     for(int i = 0; i < x-1; i++) {
//         cin >> A[i] >> B[i] >> D[i];
//     }
//     Init(x,A,B,D);
//     int y;
//     for(int i = 0; i < y1; i++) {
//         cin >> x >> y;
//         int S[x],T[y];
//         for(int i = 0; i < x; i++) {
//             cin >> S[i];
//         }
//         for(int i = 0; i < y; i++) {
//             cin >> T[i];
//         }
//         cout << Query(x,S,y,T) << endl;
//     }
// }

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