Submission #724223

#	Time	Username	Problem	Language	Result	Execution time	Memory
724223		PenguinsAreCute	Factories (JOI14_factories)	C++17	100 / 100	4908 ms	302384 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re real()
#define im imag()
#define pb push_back
#define stMn(a,b) a = min(a,b)
typedef complex<int> ii;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define MAXN 501210
#define MAXH 20
#define INF 121020103141542069
vector<ii> adj[MAXN];
int ctrP[MAXN], sbtree[MAXN], ctrH[MAXN], fEuler[MAXN], sparsetable[2*MAXN][MAXH], cnt;
int logn[2 * MAXN];
int dst[MAXN], mnDst[MAXN];
void dfs_reg(int x, int par) {
    sparsetable[cnt][0] = dst[x];
    fEuler[x] = cnt++;
    for(auto i: adj[x]) if(i.re != par) {
        dst[i.re] = dst[x] + i.im;
        dfs_reg(i.re, x);
        sparsetable[cnt++][0] = dst[x];
    }
}
void fnd() {
    logn[1] = 0;
    rep(i, 2, 2 * MAXN) logn[i] = logn[i/2] + 1;
}
void constructST() {
    rep(i, 1, MAXH) rep(j, 0, 2 * MAXN) {
        if(j <= 2 * MAXN - (1<<i)) {
            sparsetable[j][i] = min(sparsetable[j][i-1], sparsetable[j+(1<<(i-1))][i-1]);
        }
    }
}
int lca(int a, int b) {
    if(fEuler[a] > fEuler[b]) swap(a, b);
	if(a == b) sparsetable[fEuler[a]][0];
    int df = fEuler[b] - fEuler[a] + 1;
    int h = logn[df];
    return min(sparsetable[fEuler[a]][h],sparsetable[fEuler[b]+1-(1<<h)][h]);
}
int dfs_sb3(int x, int par) {
    sbtree[x] = 1;
    for(auto i: adj[x]) if(i.re != par && ctrH[i.re] == -1) {
        sbtree[x] += dfs_sb3(i.re, x);
    }
    return sbtree[x];
}
int dfs_ctr(int u, int p, int n) {
	for (auto v : adj[u]) if(ctrH[v.re] == -1) {
		if (v.re != p && sbtree[v.re] > n / 2) {
			return dfs_ctr(v.re, u, n);
		}
	}
	return u;
}
void ctr3(int u, int p, int l) {
	int n = dfs_sb3(u, p);
	int cent = dfs_ctr(u, p, n);
	ctrP[cent] = p;
	ctrH[cent] = l;
	for (auto v : adj[cent]) {
		if (ctrH[v.re] != -1) continue;
		ctr3(v.re, cent, l + 1);
	}
}
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    fnd();
    rep(i, 0, N - 1) {
        adj[A[i]].pb(ii(B[i], D[i]));
        adj[B[i]].pb(ii(A[i], D[i]));
    }
    rep(i, 0, MAXN) {
        ctrH[i] = -1;
        mnDst[i] = INF;
    }
    dfs_reg(0, -1); constructST();
    ctr3(0, -1, 0);
}
int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    vector<int> v;
    rep(i, 0, S) {
        int cur = X[i];
        while(cur != -1) {
            v.pb(cur);
            stMn(mnDst[cur], dst[cur] + dst[X[i]] - 2 * lca(cur, X[i]));
            cur = ctrP[cur];
        }
    }
    int ans = INF;
    rep(i, 0, T) {
        int cur = Y[i];
        while(cur != -1) {
            stMn(ans,mnDst[cur] + dst[cur] + dst[Y[i]] - 2 * lca(cur, Y[i]));
            cur = ctrP[cur];
        }
    }
    for(auto i: v) mnDst[i] = INF;
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int lca(long long int, long long int)':
factories.cpp:39:37: warning: statement has no effect [-Wunused-value]
   39 |  if(a == b) sparsetable[fEuler[a]][0];
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^

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