Submission #1230715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230715		quannnguyen2009	Factories (JOI14_factories)	C++20	100 / 100	1751 ms	146860 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
#define pb push_back
#define ii pair<long long, long long>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5e5+5, mod = 1e9+7, L = 19;
const long long inf = 1e18;

int timer;
vector<ii> adj[N];
vector<ii> adj_[N];
long long d[N], d_[N];
int in[N], out[N];
long long mn1[N], mn2[N];
int typ[N];
int up[N][L];

void dfs(int u, int p) {
    in[u] = ++timer;
    d_[u] = d_[p]+1;
    up[u][0] = p;
    for (int i=1; i<L; i++) up[u][i] = up[up[u][i-1]][i-1];
    for (auto [v, l]: adj[u]) {
        if (v!=p) {
            d[v] = d[u]+l;
            dfs(v, u);
        }
    }
    out[u] = timer;
}

int kth_ancestor(int u, int k) {
    for (int i=0; i<L; i++) {
        if(k>>i&1) u = up[u][i];
    }
    return u;
}

int lca(int u, int v) {
    if (d_[u]!=d_[v]) {
        if(d_[u]>d_[v]) swap(u, v);
        v = kth_ancestor(v, d_[v]-d_[u]);
    }
    if(u==v) return u;
    for (int i=L-1; i>=0; i--) {
        if (up[u][i]!=up[v][i]) {
            u = up[u][i]; v = up[v][i];
        }
    }
    return up[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
    timer = 0;
    for (int i=0; i<N-1; i++) {
        A[i]++; B[i]++;
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    dfs(1, 0);
}

bool cmp(ii a, ii b) {
    if (in[a.fi] != in[b.fi]) return in[a.fi] < in[b.fi];
    return a.se>b.se;
}

bool is_par(int u, int v) {
    return (in[u]<=in[v] && out[v]<=out[u]);
}

long long ans;

void dfs_solve(int u, int p) {
    if (typ[u]==1) mn1[u] = min(mn1[u], 0ll);
    else if (typ[u]==2) mn2[u] = min(mn2[u], 0ll);
    for (auto [v, l]: adj_[u]) {
        if (v!=p) {
            dfs_solve(v, u);
            mn1[u] = min(mn1[u], l+mn1[v]);
            mn2[u] = min(mn2[u], l+mn2[v]);
        }
    }
    ans = min(ans, mn1[u]+mn2[u]);
}

long long Query(int S, int X[], int T, int Y[]) {
    ans = inf;
    vector<ii> v;
    for (int i=0; i<S; i++) {
        X[i]++;
        v.pb({X[i], 1});
    }
    for (int i=0; i<T; i++) {
        Y[i]++;
        v.pb({Y[i], 2});
    }
    sort(all(v), cmp);
    int tmp = sz(v);
    for (int i=1; i<tmp; i++) {
        v.pb({lca(v[i].fi, v[i-1].fi), 0});
    }
    sort(all(v), cmp);
    v.erase(unique(all(v), [&](auto &a, auto &b){ return a.first == b.first; }), v.end());
    for (int i=0; i<=sz(v); i++) {
        adj_[i].clear();
        mn1[i] = mn2[i] = inf;
        typ[i] = 0;
    }
    int idx = 0;
    stack<ii> st;
    for (auto it: v) {
        while (sz(st) && !is_par(st.top().fi, it.fi)) {
            st.pop();
        }
        idx++;
        typ[idx] = it.se;
        if (sz(st)) {
            adj_[st.top().se].pb({idx, d[it.fi]-d[st.top().fi]});
            adj_[idx].pb({st.top().se, d[it.fi]-d[st.top().fi]});
        }
        st.push({it.fi, idx});
    }
    dfs_solve(1, 0);
    return ans;
}

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