Submission #47709

#	Time	Username	Problem	Language	Result	Execution time	Memory
47709		qoo2p5	Factories (JOI14_factories)	C++17	100 / 100	4703 ms	524288 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

const int N = (int) 5e5 + 123;
const int L = 20;

int n;
vector<pair<int, int>> g[N];
ll len[N];
int depth[N];
int up[N][L];
int tin[N], tout[N];

void precalc(int v, int f = 0) {
    static int tmr = 0;
    tin[v] = tmr++;
    up[v][0] = f;
    rep(i, 1, L) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto &e : g[v]) {
        int u = e.first;
        if (u == f) {
            continue;
        }
        len[u] = len[v] + e.second;
        depth[u] = depth[v] + 1;
        precalc(u, v);
    }
    tout[v] = tmr - 1;
}

bool test(int mask, int bit) {
    return mask & (1 << bit);
}

int go(int v, int h) {
    rep(i, 0, L) {
        if (test(h, i)) {
            v = up[v][i];
        }
    }
    return v;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    u = go(u, depth[u] - depth[v]);
    if (u == v) {
        return u;
    }
    per(i, L - 1, 0) {
        int uu = up[u][i], vv = up[v][i];
        if (uu != vv) {
            u = uu, v = vv;
        }
    }
    return up[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    rep(i, 0, n - 1) {
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    precalc(0);
}

vector<int> adj[N];

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

ll dp1[N], dp2[N];

ll dfs(int v) {
    ll res = LINF;
    for (int u : adj[v]) {
        mini(res, dfs(u));
        mini(dp1[v], dp1[u] + len[u] - len[v]);
        mini(dp2[v], dp2[u] + len[u] - len[v]);
    }
    mini(res, dp1[v] + dp2[v]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> p;
    rep(i, 0, S) {
        p.pb(X[i]);
    }
    rep(i, 0, T) {
        p.pb(Y[i]);
    }
    sort(all(p), [] (int i, int j) {
        return tin[i] < tin[j];
    });
    vector<int> q;
    rep(i, 0, sz(p) - 1) {
        q.pb(lca(p[i], p[i + 1]));
    }
    for (int v : q) {
        p.pb(v);
    }
    sort(all(p));
    p.resize(unique(all(p)) - p.begin());
    sort(all(p), [] (int i, int j) {
        return tin[i] < tin[j];
    });
    
    for (int v : p) {
        dp1[v] = LINF;
        dp2[v] = LINF;
        adj[v].clear();
    }
    
    vector<int> st;
    st.pb(p[0]);
    rep(i, 1, sz(p)) {
        int v = p[i];
        while (!in(v, st.back())) {
            st.pop_back();
        }
        adj[st.back()].pb(v);
        st.pb(v);
    }
    rep(i, 0, S) {
        dp1[X[i]] = 0;
    }
    rep(i, 0, T) {
        dp2[Y[i]] = 0;
    }
    return dfs(p[0]);
}

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