Submission #197504

#	Time	Username	Problem	Language	Result	Execution time	Memory
197504		handlename	Factories (JOI14_factories)	C++17	100 / 100	4209 ms	181336 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define mp make_pair
#define pb push_back
int n;
vector<pair<int,int> > adj[500001];
int sub[500001],lvl[500001],par[500001];
long long ans[500001];
long long dist[500001][19];
stack<int> st;
int dfs1(int u,int p,int l){
    sub[u]=1; // Subtree size is 1
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        // Already added to centroid tree
        if (i.first==p) continue;
        if (l>0) dist[i.first][l-1]=dist[u][l-1]+i.second;
        sub[u]+=dfs1(i.first,u,l);
        // Increase size of subtree
    }
    return sub[u];
}
int dfs2(int u,int p,int sn){
    // Pass in the size of the subtree
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        // Already added to centroid tree
        if (i.first==p) continue;
        if (sub[i.first]>sn/2){
            return dfs2(i.first,u,sn);
        }
    }
    return u; // No child has size more than n/2 , hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u,int p,int l){
    int cn=dfs1(u,p,l);
    int cent=dfs2(u,p,cn);
    if (p==-1) p=cent;
    par[cent]=p;
    lvl[cent]=l;
    for (auto i:adj[cent]){
        if (lvl[i.first]!=-1) continue;
        dist[i.first][l]=i.second;
        build(i.first,cent,l+1);
    }
}
void upd(int x){
    int l=lvl[x];
    int y=x;
    while (l!=-1){
        ans[y]=min(ans[y],dist[x][l]);
        // Check the shortest distance against the distance between the current node
        st.push(y);
        y=par[y];
        // Traverse up the centroid tree
        l--;
        // Keep track of which parent we are on
    }
}
long long qry(int x){
    long long res=1e16;
    int l=lvl[x];
    int y=x;
    while (l!=-1){
        res=min(res,ans[y]+dist[x][l]);
        y=par[y];
        l--;
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0;i<n-1;i++){
        adj[A[i]].pb(mp(B[i],D[i]));
        adj[B[i]].pb(mp(A[i],D[i]));
    }
    memset(lvl,-1,sizeof(lvl));
    build(0,-1,0);
    for (int i=0;i<n;i++) ans[i]=1e16;
}
long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0;i<S;i++) upd(X[i]);
    long long res=1e16;
    for (int i=0;i<T;i++) res=min(res,qry(Y[i]));
    while (!st.empty()){
        ans[st.top()]=1e16;
        st.pop();
    }
    return res;
}

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