Submission #227855

#	Time	Username	Problem	Language	Result	Execution time	Memory
227855		tri	Factories (JOI14_factories)	C++14	33 / 100	8096 ms	110940 KiB

factories

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int LOGN = 19;
const int MAXN = 5e5 + 100;
const ll INF = 1e15;

vector<pi> aL[MAXN];

int anc[MAXN][LOGN];
int depth[MAXN];
ll rDist[MAXN];

int N;

void dfs(int cV, int pV) {
    for (pi aE : aL[cV]) {
        int aV = aE.f;
        ll eC = aE.s;
        if (aV != pV) {
            depth[aV] = depth[cV] + 1;
            rDist[aV] = rDist[cV] + eC;
            dfs(aV, cV);
            anc[aV][0] = cV;
        }
    }
}

void prep() {
    anc[0][0] = 0;
    for (int k = 1; k < LOGN; k++) {
        for (int i = 0; i < N; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
        }
    }
}

int j(int a, int d) {
    for (int i = 0; i < LOGN; i++) {
        if (d & (1 << i)) {
            a = anc[a][i];
        }
    }
    return a;
}

int fLCA(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);

    b = j(b, depth[b] - depth[a]);

    if (a == b) return a;

    for (int i = LOGN - 1; i >= 0; i--) {
        if (anc[a][i] != anc[b][i]) {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}


void Init(int iN, int A[], int B[], int D[]) {
    N = iN;
    for (int i = 0; i < N; i++) {
        aL[A[i]].pb({B[i], D[i]});
        aL[B[i]].pb({A[i], D[i]});
    }
    depth[0] = rDist[0] = 0;
    dfs(0, -1);
    prep();
}

ll ans;
ll best[MAXN][2];

void dfsAll(int cV, int pV) {
    for (pi aE : aL[cV]) {
        int aV = aE.f;
        ll eC = aE.s;
        if (aV != pV) {
            dfsAll(aV, cV);
            best[cV][0] = min(best[cV][0], best[aV][0] + eC);
            best[cV][1] = min(best[cV][1], best[aV][1] + eC);
        }
        ans = min(ans, best[cV][0] + best[cV][1]);
    }
}

ll Query(int S, int X[], int T, int Y[]) {
    vi x(X, X + S);
    vi y(Y, Y + T);

    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(y.begin(), y.end()), y.end());

    S = x.size(), T = y.size();

    ans = INF;
    if (S * T >= 1e4) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2; j++) {
                best[i][j] = INF;
            }
        }

        for (int i = 0; i < S; i++) {
            best[x[i]][0] = 0;
        }
        for (int i = 0; i < T; i++) {
            best[y[i]][1] = 0;
        }

        dfsAll(0, -1);
    } else {
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++) {
                int lca = fLCA(x[i], y[j]);
                ll cur = rDist[x[i]] + rDist[y[j]] - 2 * rDist[lca];
                ans = min(ans, cur);
            }
        }
    }
    assert(ans >= 0);
    return ans;
}

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