Submission #171120

#	Time	Username	Problem	Language	Result	Execution time	Memory
171120		dantoh000	Factories (JOI14_factories)	C++14	100 / 100	5933 ms	169792 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int SZ = 500005;
const ll INF = 1000000000000000000;
int par[SZ], lvl[SZ], sub[SZ];
ll dist[SZ][20], ans[SZ];
vector<ii> adjlist[SZ];
stack<int> st;
int dfs1(int u, int p, int l){
    sub[u] = 1;
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        sub[u] += dfs1(v.fi,u,l);
    }
    return sub[u];
}
int dfs2(int u, int p, int n){
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        if (sub[v.fi] > n/2) return dfs2(v.fi,u,n);
    }
    return u;
}
void dfs3(int u, int p, int l, ll d){
    //printf("dist %d %d = %lld\n",u,l,d);
    dist[u][l] = d;
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        dfs3(v.fi,u,l,d+v.se);
    }
}
void build(int u, int p, int l){
    int n = dfs1(u,p,l);
    int cent = dfs2(u,p,n);
    dfs3(cent,-1,l,0);
    if (p == -1) p = cent;
    //printf("built %d %d %d\n",cent,p,l);
    par[cent] = p;
    lvl[cent] = l;
    for (auto v : adjlist[cent]){
        if (lvl[v.fi] != -1) continue;
        build(v.fi,cent,l+1);
    }
}
void update(int x){
    int l = lvl[x];
    int y = x;
    while (l != -1){
        //printf("updating %d %d: %lld\n",x,y,dist[x][l]);
        ans[y] = min(ans[y],dist[x][l]);
        st.push(y);
        y = par[y];
        l--;
    }
}
ll query(int x){
    ll res = INF;
    int l = lvl[x];
    int y = x;
    while (l != -1){
        //printf("at %d (level %d), nearest is %d\n",y,l,ans[y]);
        res = min(res,ans[y]+dist[x][l]);
        y = par[y];
        l--;
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]){
    memset(ans,127,sizeof(ans));
    memset(lvl,-1,sizeof(lvl));
    for (int i = 0; i < N-1; i++){
        adjlist[A[i]].push_back(ii(B[i],D[i]));
        adjlist[B[i]].push_back(ii(A[i],D[i]));
    }
    build(0,-1,0);
}
ll Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < S; i++){
        update(X[i]);
    }
    ll res = INF;
    for (int i = 0; i < T; i++){
        res = min(res,query(Y[i]));
    }
    while (st.size()){
        ans[st.top()] = INF;
        st.pop();
    }
    return res;
}

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