oj.uz

Submission #724223

# Submission time Handle Problem Language Result Execution time Memory
724223 2023-04-14T22:22:50 Z PenguinsAreCute Factories (JOI14_factories) C++17
100 / 100
 4908 ms 302384 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 185312 KB Output is correct
2 Correct 606 ms 202808 KB Output is correct
3 Correct 691 ms 202808 KB Output is correct
4 Correct 689 ms 203488 KB Output is correct
5 Correct 771 ms 203360 KB Output is correct
6 Correct 508 ms 202656 KB Output is correct
7 Correct 681 ms 202700 KB Output is correct
8 Correct 680 ms 202884 KB Output is correct
9 Correct 759 ms 203348 KB Output is correct
10 Correct 499 ms 202640 KB Output is correct
11 Correct 743 ms 202768 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 184868 KB Output is correct
2 Correct 2119 ms 257812 KB Output is correct
3 Correct 2925 ms 259628 KB Output is correct
4 Correct 996 ms 254920 KB Output is correct
5 Correct 3673 ms 285244 KB Output is correct
6 Correct 2990 ms 261864 KB Output is correct
7 Correct 1666 ms 218032 KB Output is correct
8 Correct 755 ms 217948 KB Output is correct
9 Correct 1820 ms 222152 KB Output is correct
10 Correct 1645 ms 219444 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 185312 KB Output is correct
2 Correct 606 ms 202808 KB Output is correct
3 Correct 691 ms 202808 KB Output is correct
4 Correct 689 ms 203488 KB Output is correct
5 Correct 771 ms 203360 KB Output is correct
6 Correct 508 ms 202656 KB Output is correct
7 Correct 681 ms 202700 KB Output is correct
8 Correct 680 ms 202884 KB Output is correct
9 Correct 759 ms 203348 KB Output is correct
10 Correct 499 ms 202640 KB Output is correct
11 Correct 743 ms 202768 KB Output is correct
12 Correct 271 ms 184868 KB Output is correct
13 Correct 2119 ms 257812 KB Output is correct
14 Correct 2925 ms 259628 KB Output is correct
15 Correct 996 ms 254920 KB Output is correct
16 Correct 3673 ms 285244 KB Output is correct
17 Correct 2990 ms 261864 KB Output is correct
18 Correct 1666 ms 218032 KB Output is correct
19 Correct 755 ms 217948 KB Output is correct
20 Correct 1820 ms 222152 KB Output is correct
21 Correct 1645 ms 219444 KB Output is correct
22 Correct 3055 ms 272596 KB Output is correct
23 Correct 2926 ms 281032 KB Output is correct
24 Correct 3940 ms 282380 KB Output is correct
25 Correct 4054 ms 284108 KB Output is correct
26 Correct 4061 ms 268416 KB Output is correct
27 Correct 4908 ms 302384 KB Output is correct
28 Correct 1160 ms 266924 KB Output is correct
29 Correct 3964 ms 267828 KB Output is correct
30 Correct 3954 ms 267596 KB Output is correct
31 Correct 3927 ms 268216 KB Output is correct
32 Correct 2119 ms 234880 KB Output is correct
33 Correct 739 ms 219324 KB Output is correct
34 Correct 1311 ms 215996 KB Output is correct
35 Correct 1362 ms 215832 KB Output is correct
36 Correct 1658 ms 216612 KB Output is correct
37 Correct 1563 ms 216532 KB Output is correct