oj.uz

Submission #883877

# Submission time Handle Problem Language Result Execution time Memory
883877 2023-12-06T10:33:37 Z chanhchuong123 Factories (JOI14_factories) C++17
100 / 100
 4319 ms 178840 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const long long INF = 1e18 + 7;
const int MAX = 500005;
int n, q;
int timer;
int h[MAX];
int fr[MAX];
int to[MAX];
int co[MAX];
int sz[MAX];
int tin[MAX];
int par[MAX];
bool rem[MAX];
long long dep[MAX];
long long dist[MAX];
int dp[20][MAX << 1];
vector<int> adj[MAX];
#define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))

void dfs(int u, int p) {
    dp[0][timer] = u;
    tin[u] = timer++;
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            dep[v] = dep[u] + co[id];
            h[v] = h[u] + 1;
            dfs(v, u);
            dp[0][timer++] = u;
        }
    }
}

int LCA(int u, int v) {
    int l = tin[u], r = tin[v]; if (l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    return COMBINE(dp[k][l], dp[k][r - (1 << k) + 1]);
}

long long DIST(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            sz[u] += dfsSZ(v, u);
        }
    }
    return sz[u];
}

int findCentroid(int u, int p, int n) {
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            if ((sz[v] << 1) > n)
                return findCentroid(v, u, n);
        }
    }
    return u;
}

void solve(int u, int p) {
    int c = findCentroid(u, p, dfsSZ(u, p));
    dist[c] = INF;
    rem[c] = true;
    par[c] = p;
    for (int &id: adj[c]) {
        int v = fr[id] ^ to[id] ^ c;
        if (v != p && rem[v] == 0) {
            solve(v, c);
        }
    }
}

void Init(int _n, int _a[], int _b[], int _d[]) {
    n = _n;
    for (int i = 0; i < n - 1; ++i) {
        fr[i] = _a[i];
        to[i] = _b[i];
        co[i] = _d[i];
        adj[fr[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    dfs(0,   -1);
    for (int j = 1; (1 << j) <= timer; ++j) {
        for (int i = 0; i + (1 << j) - 1 <= timer - 1; ++i)
            dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
    }
    solve(0, -1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        for (int cur = X[i]; cur != -1; cur = par[cur])
                dist[cur] = min(dist[cur], DIST(X[i], cur));
    }
    long long res = INF;
    for (int i = 0; i < T; ++i) {
        for (int cur = Y[i]; cur != -1; cur = par[cur])
                res = min(res, dist[cur] + DIST(Y[i], cur));
    }
    for (int i = 0; i < S; ++i) {
        for (int cur = X[i]; cur != -1; cur = par[cur])
            dist[cur] = INF;
    }
    return res;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   97 |             dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                  ~~^~~
factories.cpp:24:37: note: in definition of macro 'COMBINE'
   24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
      |                                     ^
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   97 |             dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                  ~~^~~
factories.cpp:24:50: note: in definition of macro 'COMBINE'
   24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
      |                                                  ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62044 KB Output is correct
2 Correct 274 ms 76676 KB Output is correct
3 Correct 343 ms 76996 KB Output is correct
4 Correct 340 ms 76624 KB Output is correct
5 Correct 412 ms 77136 KB Output is correct
6 Correct 162 ms 76628 KB Output is correct
7 Correct 339 ms 76924 KB Output is correct
8 Correct 347 ms 76676 KB Output is correct
9 Correct 419 ms 77044 KB Output is correct
10 Correct 168 ms 76624 KB Output is correct
11 Correct 332 ms 76628 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 62044 KB Output is correct
2 Correct 1543 ms 151892 KB Output is correct
3 Correct 1974 ms 154512 KB Output is correct
4 Correct 490 ms 153284 KB Output is correct
5 Correct 3237 ms 178840 KB Output is correct
6 Correct 2125 ms 154760 KB Output is correct
7 Correct 743 ms 102796 KB Output is correct
8 Correct 261 ms 103364 KB Output is correct
9 Correct 939 ms 106068 KB Output is correct
10 Correct 744 ms 103256 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62044 KB Output is correct
2 Correct 274 ms 76676 KB Output is correct
3 Correct 343 ms 76996 KB Output is correct
4 Correct 340 ms 76624 KB Output is correct
5 Correct 412 ms 77136 KB Output is correct
6 Correct 162 ms 76628 KB Output is correct
7 Correct 339 ms 76924 KB Output is correct
8 Correct 347 ms 76676 KB Output is correct
9 Correct 419 ms 77044 KB Output is correct
10 Correct 168 ms 76624 KB Output is correct
11 Correct 332 ms 76628 KB Output is correct
12 Correct 9 ms 62044 KB Output is correct
13 Correct 1543 ms 151892 KB Output is correct
14 Correct 1974 ms 154512 KB Output is correct
15 Correct 490 ms 153284 KB Output is correct
16 Correct 3237 ms 178840 KB Output is correct
17 Correct 2125 ms 154760 KB Output is correct
18 Correct 743 ms 102796 KB Output is correct
19 Correct 261 ms 103364 KB Output is correct
20 Correct 939 ms 106068 KB Output is correct
21 Correct 744 ms 103256 KB Output is correct
22 Correct 2153 ms 150964 KB Output is correct
23 Correct 2220 ms 152144 KB Output is correct
24 Correct 3058 ms 153180 KB Output is correct
25 Correct 3066 ms 155044 KB Output is correct
26 Correct 3193 ms 153636 KB Output is correct
27 Correct 4319 ms 172932 KB Output is correct
28 Correct 651 ms 153316 KB Output is correct
29 Correct 3115 ms 153260 KB Output is correct
30 Correct 2958 ms 152860 KB Output is correct
31 Correct 2986 ms 153468 KB Output is correct
32 Correct 933 ms 106636 KB Output is correct
33 Correct 263 ms 102820 KB Output is correct
34 Correct 560 ms 101716 KB Output is correct
35 Correct 566 ms 101768 KB Output is correct
36 Correct 774 ms 102248 KB Output is correct
37 Correct 746 ms 102232 KB Output is correct