Submission #1283602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283602		wonderful	Factories (JOI14_factories)	C++20	0 / 100	1562 ms	139944 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

int a,b;
vector<pair<int,int>> z[1000005];
int child[1000005];
int del[1000005];
int sz;
int par[1000005];
int high[1000005];
long long cnt[500005][21];
int cur=0;
long long inf=1e16;
long long sad[1000005];
vector<int> v;
vector<int> v1;

void predfs(int i,int parent){
    child[i]=1;
    for (auto [p,w]:z[i]){
        if (p==parent || del[p]) continue;
        predfs(p,i);
        child[i]+=child[p];
    }
}

int centroid(int i,int parent){
    for (auto [p,w]:z[i]){
        if (p==parent || del[p]) continue;
        if (child[p]*2>sz) return centroid(p,i);
    }
    return i;
}

void dfs(int i,int parent,int depth){
    cnt[i][cur]=depth;
    for (auto [p,w]:z[i]){
        if (p==parent || del[p]) continue;
        dfs(p,i,depth+w);
    }
}

void decompose(int i,int parent){
    predfs(i,i);
    sz=child[i];
    int cen=centroid(i,i);
    del[cen]=1;
    high[cen]=high[parent]+1;
    par[cen]=parent;
    cur=high[cen];
    cnt[cen][cur]=0;
    for (auto [p,w]:z[cen]){
        if (del[p]) continue;
        dfs(p,cen,w);
    }
    for (auto [p,w]:z[cen]){
        if (del[p]) continue;
        decompose(p,cen);
    }
}


void Init(int N, int A[], int B[], int D[]){
    a=N;
    for (int i=1;i<=a;i++){
        z[i].clear();
        del[i]=0;
        high[i]=0;
        par[i]=0;
    }
    for (int i=0;i<a-1;i++){
        int x=A[i]+1;
        int y=B[i]+1;
        int t=D[i];
        z[x].push_back({y,t});
        z[y].push_back({x,t});
    }
    decompose(1,0);
    for (int i=1;i<=a;i++) sad[i]=-1;
}

long long Query(int S, int X[], int T, int Y[]){
    v.clear(); v1.clear();
    for (int i=0;i<S;i++) v.push_back(X[i]+1);
    for (int i=0;i<T;i++) v1.push_back(Y[i]+1);
    long long min1=inf;
    for (auto x:v){
        int p=x;
        while (p!=0){
            if (sad[p]==-1) sad[p]=cnt[x][high[p]];
            else sad[p]=min(sad[p],cnt[x][high[p]]);
            p=par[p];
        }
    }
    for (auto x:v1){
        int p=x;
        while (p!=0){
            if (sad[p]!=-1) min1=min(min1,cnt[x][high[p]]+sad[p]);
            p=par[p];
        }
    }
    for (auto x:v){
        int p=x;
        while (p!=0){
            sad[p]=-1;
            p=par[p];
        }
    }
    v.clear();
    v1.clear();
    return min1;
}

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