Submission #1256176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256176		ZeroCool	Factories (JOI14_factories)	C++20	100 / 100	5279 ms	379528 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
//#define int long long

const int N = 5e5 + 20;
const int LOG = 20;

vector<ar<int,2>> g[N];
ll d[N];
int dep[N];
int up[N][LOG];

void chmin(ll &x,ll y){
    x = min(x, y);
}

void dfs(int x,int p){
    up[x][0] = p;
    for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
    for(auto [u, w]: g[x]){
        if(u == p)continue;
        d[u] = d[x] + w;
        dep[u] = dep[x] + 1;
        dfs(u, x);
    }
}

int lca(int a,int b){
    if(dep[a] < dep[b])swap(a, b);
    int k = dep[a] - dep[b];
    for(int i = 0;i < LOG;i++){
        if((1 << i) & k)a = up[a][i];
    }
    if(a == b)return a;
    for(int i = LOG - 1;i >= 0;i--){
        if(up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

ll qry(int a, int b){
    int l = lca(a, b);
    return d[a] + d[b] - 2 * d[l];
}

bool del[N];
int par[N];
int sz[N];

int dfs1(int x,int p){
    sz[x] = 1;
    for(auto [u, w]: g[x]){
        if(u == p || del[u])continue;
        sz[x] += dfs1(u, x);
    }
    return sz[x];
}

int C(int x,int p,int s){
    for(auto [u, w]: g[x]){
        if(u == p || del[u])continue;
        if(sz[u] > s)return C(u, x, s);
    }
    return x;
}

void cc(int x,int p){
    int s = dfs1(x, x);
    x = C(x, x, s / 2);
    del[x] = 1;
    par[x] = p;
    for(auto [u, w]: g[x]){
        if(del[u])continue;
        cc(u, x);
    }
}

ll mn[N];

int nn;

vector<pair<int,ll>> go[N];

void Init(signed n, signed A[], signed B[], signed D[]) {
    nn = n;
    for(int i = 0;i < n - 1;i++){
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    cc(0, -1);
   // for(int i = 0;i < n;i++)cout<<par[i]<<" ";
    //cout<<'\n';
  //  cout<<"what"<<lca(1, 6)<<'\n';
    for(int i = 0;i < n;i++)mn[i] = 1e17;
    for(int i = 0;i < n;i++){
        int x = i;
        while(x != -1){
            go[i].push_back({x, qry(x, i)});
            x = par[x];
        }
    }
    //assert(0);
}

long long Query(signed n, signed X[], signed m, signed Y[]) {
    set<int> s;
    for(int i = 0;i < n;i++){
        for(auto [x, d]: go[X[i]]){
           // cout<<x<<" ";
            s.insert(x);
            chmin(mn[x], d);
           // x = par[x];
        }
        //cout<<'\n';
    }
   // for(int i = 0;i < nn;i++)cout<<mn[i]<<" ";
   // cout<<'\n';
    ll ans = 1e17;
    for(int i = 0;i < m;i++){
        for(auto [x, d]: go[Y[i]]){
           // cout<<x<<" ";
            chmin(ans, mn[x] + d);
            //x = par[x];
        }
       // cout<<'\n';
    }
    for(auto u: s)mn[u] = 1e17;
    return ans;
}


#define int signed

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