Submission #52310

#	Time	Username	Problem	Language	Result	Execution time	Memory
52310		Diuven	Factories (JOI14_factories)	C++11	100 / 100	7532 ms	351568 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MX=500010, LG=20;
const ll inf=2e17;

struct edge {
    int to; ll co;
};

int n, dep[MX];
vector<edge> G[MX];

vector<edge> C, D[MX];
bool done[MX];


int sub[MX];
void dfs(int v, int p=-1){
    sub[v]=1;
    for(edge &e:G[v]){
        int x=e.to;
        if(done[x] || x==p) continue;
        dfs(x,v);
        sub[v]+=sub[x];
    }
}

int findcen(int v, int sz){
    for(edge &e:G[v]){
        int x=e.to;
        if(done[x] || sub[x]>sub[v]) continue;
        if(sub[x]*2>sz) return findcen(x,sz);
    }
    return v;
}
int now;
void dfs2(int v, int p, ll d){
    D[v].push_back({now, d});
    for(edge &e:G[v]){
        int x=e.to; ll c=e.co;
        if(done[x] || x==p) continue;
        dfs2(x,v,d+c);
    }
}

ll mn1[MX], mn2[MX];

void process(int v=1){
    dfs(v,0);
    v=findcen(v,sub[v]); done[v]=true;
    now=v;
    for(edge &e:G[v]){
        int x=e.to; ll c=e.co;
        if(done[x]) continue;
        dfs2(x,v,c);
    }
    D[v].push_back({v,0});
    for(edge &e:G[v]){
        int x=e.to;
        if(done[x]) continue;
        process(x);
    }
}

void Init(int N, int A[], int B[], int D[]){
    n=N;
    fill(mn1, mn1+n+1, inf);
    fill(mn2, mn2+n+1, inf);
    for(int i=0; i<=n-2; i++){
        int u=A[i]+1, v=B[i]+1;
        G[u].push_back({v,D[i]});
        G[v].push_back({u,D[i]});
    }
    process();
}

ll Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; i++) X[i]++;
    for(int i=0; i<T; i++) Y[i]++;

    vector<int> V, W;

    for(int i=0; i<S; i++){
        for(edge &e:D[X[i]])
            V.push_back(e.to), mn1[e.to]=min(mn1[e.to], e.co);
    }
    for(int i=0; i<T; i++){
        for(edge &e:D[Y[i]])
            W.push_back(e.to), mn2[e.to]=min(mn2[e.to], e.co);
    }
    ll ans=inf;
    for(int v:V) ans=min(ans, mn1[v]+mn2[v]);
    for(int w:W) ans=min(ans, mn1[w]+mn2[w]);
    for(int v:V) mn1[v]=inf;
    for(int w:W) mn2[w]=inf;
    return ans;
}

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