Submission #558629

#	Time	Username	Problem	Language	Result	Execution time	Memory
558629		ddy888	Factories (JOI14_factories)	C++17	100 / 100	6267 ms	205156 KiB

factories

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;

#include "factories.h"

const int MAXN = 500010, LOG = 20;
const ll INF = 1e18;
int n;
vector<pi> g[MAXN];

int tk[MAXN][LOG];
int dep[MAXN];
ll wd[MAXN];
int vis[MAXN];
ll close[MAXN];
ll dst[MAXN][LOG];

void dfs(int x, int pa) {
    dep[x] = dep[pa] + 1;
    vis[x] = 1;
    tk[x][0] = pa;
    for (int i = 1; i < LOG; ++i) {
        if (tk[x][i - 1] == -1) 
            continue;
        tk[x][i] = tk[tk[x][i - 1]][i - 1];
    }
    for (auto i: g[x]) {
        if (i.fi == pa || vis[i.fi])
            continue;
        wd[i.fi] = wd[x] + i.si;
        dfs(i.fi, x);
    }
}

int jump(int x, int d) {
    for (int i = 0; i < LOG; ++i) {
        if (x == -1)
            return -1;
        if (d & (1 << i))
            x = tk[x][i];
    }
    return x;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) // wlog x is further from root
        swap(x, y);
    x = jump(x, dep[x] - dep[y]);
    if (x == y)
        return x;
    for (int i = LOG - 1; i >= 0; --i) {
        int nx = tk[x][i], ny = tk[y][i];
        if (nx == -1 || ny == -1)
            continue;
        if (nx != ny) 
            x = nx, y = ny;
    }
    return tk[x][0];
}

ll dist(int x, int y) {
    return wd[x] + wd[y] - 2 * wd[lca(x, y)];
}

struct CentroidDecomposition {
    vector<int> sub;
    vector<int> rem;
    vector<int> tree;
    vector<int> lvl;

    void init(int nodes) {
        sub.resize(nodes + 1);
        rem.resize(nodes + 1);
        lvl.resize(nodes + 1);
        tree.resize(nodes + 1, -1);
        build(0, -1, 0);
    }

    int dfs(int u, int p) {
        sub[u] = 1;
        for (auto i: g[u]) {
            if (i.fi == p || rem[i.fi])
                continue;
            sub[u] += dfs(i.fi, u);
        }
        return sub[u];
    }

    int cent(int u, int sz, int p) {
        for (auto i: g[u]) {
            if (i.fi == p || rem[i.fi])
                continue;
            if (sub[i.fi] * 2 <= sz)
                continue;
            return cent(i.fi, sz, u);
        }
        return u;
    }

    void build(int u, int p, int l) {
        int c = cent(u, dfs(u, -1), -1);
        rem[c] = 1;
        tree[c] = p;    
        lvl[c] = l;
        for (auto i: g[c]) {
            if (rem[i.fi])
                continue;
            build(i.fi, c, l + 1);
        }
    }

    int par(int u) {
        return tree[u];
    }

    int level(int u) {
        return lvl[u];
    }
} cd;

void Init(int _N, int _A[], int _B[], int _D[]) {
    n = _N;
    for (int i = 0; i < n - 1; ++i) {
        int u = _A[i], v = _B[i], c = _D[i];
        // ++u, ++v;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    memset(tk, -1, sizeof tk);
    dfs(0, -1);
    cd.init(n + 1);
    for (int i = 0; i < n; ++i) {
        int v = i;
        for (int j = cd.lvl[i]; j >= 0; --j) {
            dst[i][j] = dist(i, v);
            v = cd.par(v);
        }   
    }
    for (int i = 0; i < n; ++i)
        close[i] = INF;
}

long long Query(int _S, int _X[], int _T, int _Y[]) {
    for (int i = 0; i < _S; ++i) {
        int node = _X[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            close[v] = min(close[v], dst[x][l]);
        }
    }
    ll ans = INF;
    for (int i = 0; i < _T; ++i) {
        int node = _Y[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            ans = min(ans, close[v] + dst[x][l]);
        }
    }
    for (int i = 0; i < _S; ++i) {
        int node = _X[i];
        int x = node, v = node;
        for (int l = cd.level(x); l >= 0; --l, v = cd.par(v)) {
            close[v] = INF;
        }
    }
    return ans;
}

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