Submission #393185

#	Time	Username	Problem	Language	Result	Execution time	Memory
393185		jeroenodb	Factories (JOI14_factories)	C++17	0 / 100	2781 ms	213884 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 5e5+1;
const ll oo = 1e9;
vector<pair<int,ll>> adj[mxN];
int sz[mxN];
bitset<mxN> visited;
struct anc {
    int i;
    ll d;
};
vector<anc> ancs[mxN];
int curcentroid;
void dfsz(int at,int from=-1) {
    sz[at]=1;
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsz(to,at);
        sz[at]+=sz[to];
    }
}
void dfsd(int at,int from=-1,ll d=0) {
    ancs[at].push_back({curcentroid,d});
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsd(to,at,w+d);
    }
}
int centroid(int at) {
    int from=-1,total=sz[at];
    bool done = false;
    while(!done) {
        done = true;
        for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
            if(sz[to]*2>total) {
                from = at;
                at = to;
                done = false;
                break;
            }
        }
    }
    return at;
}
void decomp(int at) {
    dfsz(at);
    int c = curcentroid = centroid(at);
    dfsd(c);

    visited[c] = true;
    for(auto [to,w]: adj[c]) if(!visited[to]) {
        decomp(to);
    }
    visited[c]= false;
}
ll mn[mxN];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;++i) {
        adj[i].clear();
        ancs[i].clear();
    }
    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]});
    }
    decomp(0);
    fill(mn,mn+N,oo);
}


int st[mxN],p;
long long Query(int S, int X[], int T, int Y[]) {
    p=0;
    for(int i=0;i<S;++i) {
        for(auto& a : ancs[X[i]]) {
            if(mn[a.i]==oo) {
                st[p++]=a.i;  
            }
            mn[a.i] = min(mn[a.i],a.d);
        }
    }
    ll ans = oo;
    for(int i=0;i<T;++i) {
        for(auto& a : ancs[Y[i]]) {
            ans = min(ans, mn[a.i]+a.d);
        }
    }
    for(int i=0;i<p;++i) {
        mn[st[i]] = oo;
    }
    return ans;
}

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