Submission #40249

#	Time	Username	Problem	Language	Result	Execution time	Memory
40249		krauch	Factories (JOI14_factories)	C++14	0 / 100	6000 ms	243260 KiB

factories

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

using namespace std;

typedef long long ll;

#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second

const ll ool = 1e18 + 9;
const int N = 5e5 + 6, C = 20, oo = 1e9 + 9;

int n, tin[N], tp[N], timer, lg[N];
ll lvl[N], d[N][2];
pair < int, ll > mn[N][C + 1];
vector < pair < int, ll > > g[N];

void dfs(int v, int par) {
    tin[v] = ++timer;
    mn[0][timer] = mkp(v, lvl[v]);
    for (auto it : g[v]) {
        int to = it.F;
        if (to == par) continue;
        lvl[to] = lvl[v] + it.S;
        dfs(to, v);
        mn[0][++timer] = mkp(v, lvl[v]);
    }
}

ll dfs2(int v, int par) {
    d[v][0] = d[v][1] = ool;
    ll res = ool;
    if (tp[v] == 1) d[v][0] = 0;
    if (tp[v] == 2) d[v][1] = 0;
    for (auto it : g[v]) {
        int to = it.F;
        if (to == par) continue;
        res = min(res, dfs2(to, v));
        d[v][0] = min(d[v][0], d[to][0] + it.S);
        d[v][1] = min(d[v][1], d[to][1] + it.S);
    }
    return min(res, d[v][0] + d[v][1]);
}

int get(int l, int r) {
    if (l > r) swap(l, r);
    int deg = lg[r - l + 1];
    return min(mn[deg][l], mn[deg][r - (1 << deg) + 1]).S;
}

void Init(int _n, int A[], int B[], int D[]) {
    n = _n;
    forn(i, 0, n - 2) {
        g[A[i] + 1].eb(B[i] + 1, D[i]);
        g[B[i] + 1].eb(A[i] + 1, D[i]);
    }
    dfs(1, 0);
    forn(i, 1, C) {
        forn(j, 1, timer - (1 << i) + 1) {
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
    forn(i, 2, timer) lg[i] = lg[i >> 1] + 1;
}

ll Query(int S, int X[], int T, int Y[]) {
    if (S <= 10 && T <= 10) {
        ll res = ool;
        forn(i, 0, S - 1) {
            forn(j, 0, T - 1) {
                int v = X[i] + 1, u = Y[j] + 1;
                int lca = get(tin[u], tin[v]);
                res = min(res, lvl[u] + lvl[v] - 2 * lvl[lca]);
            }
        }
        return res;
    }
    forn(i, 0, S - 1)
        tp[X[i] + 1] = 1;
    forn(i, 0, T - 1)
        tp[Y[i] + 1] = 2;
    ll res = dfs2(1, 0);
    forn(i, 0, S - 1)
        tp[X[i] + 1] = 0;
    forn(i, 0, T - 1)
        tp[Y[i] + 1] = 0;
    return res;
}

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