oj.uz

Submission #969547

# Submission time Handle Problem Language Result Execution time Memory
969547 2024-04-25T09:50:30 Z Turkhuu Factories (JOI14_factories) C++17
100 / 100
 5242 ms 243036 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int I = 5e5;
int N;
ll len[I], best[I];
int p[I], sz[I], in[I], vis[I], dep[I], par[I][20], st[2 * I][20];
vector<int> a;
vector<array<int, 2>> adj[I];
void dfs(int x, int p) {
    in[x] = a.size();
    a.push_back(x);
    for (int i = 0; i < 18 && par[x][i] != -1; i++) {
        par[x][i + 1] = par[par[x][i]][i];
    }
    for (auto [y, z] : adj[x]) {
        if (y == p) continue;
        par[y][0] = x;
        dep[y] = dep[x] + 1;
        len[y] = len[x] + z;
        dfs(y, x);
        a.push_back(x);
    }
}
void init(int x, int p) {
    sz[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        init(y, x);
        sz[x] += sz[y];
    }
}
int find(int x, int p, int s) {
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        if (sz[y] * 2 > s) return find(y, x, s);
    }
    return x;
}
int cd(int x) {
    init(x, -1);
    x = find(x, -1, sz[x]);
    vis[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (!vis[y]) {
            p[cd(y)] = x;
        }
    }
    return x;
}
int f(int x, int y) {
    return (x != -1 && (y == -1 || dep[x] < dep[y])) ? x : y;
}
void build() {
    for (int i = 0; i < a.size(); i++) {
        st[i][0] = a[i];
    }
    for (int j = 0; j < 19; j++) {
        for (int i = 0; i + (2 << j) <= a.size(); i++) {
            st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
        }
    }
}
int query(int l, int r) {
    int k = __lg(r - l);
    return f(st[l][k], st[r - (1 << k)][k]);
}
int lca(int x, int y) {
    return query(min(in[x], in[y]), max(in[x], in[y]) + 1);
}
ll dis(int x, int y) {
    return len[x] + len[y] - 2 * len[lca(x, y)];
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (int i = 0; i < 2 * N; i++) {
        for (int j = 0; j < 20; j++) {
            st[i][j] = -1;
        }
    }
    for (int i = 0; i < N; i++) {
        best[i] = 1e18;
        for (int j = 0; j < 20; j++) {
            par[i][j] = -1;
        }
    }
    dfs(0, -1);
    build();
    p[cd(0)] = -1;
}
ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = min(best[j], dis(j, X[i]));
        }
    }
    ll ans = 1e18;
    for (int i = 0; i < T; i++) {
        for (int j = Y[i]; j != -1; j = p[j]) {
            ans = min(ans, best[j] + dis(j, Y[i]));
        }
    }
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = 1e18;
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void build()':
factories.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
factories.cpp:60:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i + (2 << j) <= a.size(); i++) {
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41560 KB Output is correct
2 Correct 312 ms 48008 KB Output is correct
3 Correct 365 ms 48016 KB Output is correct
4 Correct 367 ms 48208 KB Output is correct
5 Correct 454 ms 48520 KB Output is correct
6 Correct 211 ms 48020 KB Output is correct
7 Correct 358 ms 48212 KB Output is correct
8 Correct 365 ms 48264 KB Output is correct
9 Correct 463 ms 48496 KB Output is correct
10 Correct 186 ms 48016 KB Output is correct
11 Correct 393 ms 48016 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41564 KB Output is correct
2 Correct 1682 ms 193132 KB Output is correct
3 Correct 2416 ms 196952 KB Output is correct
4 Correct 664 ms 212152 KB Output is correct
5 Correct 3248 ms 243036 KB Output is correct
6 Correct 2413 ms 215520 KB Output is correct
7 Correct 1209 ms 95416 KB Output is correct
8 Correct 483 ms 95100 KB Output is correct
9 Correct 1241 ms 98728 KB Output is correct
10 Correct 1103 ms 95892 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41560 KB Output is correct
2 Correct 312 ms 48008 KB Output is correct
3 Correct 365 ms 48016 KB Output is correct
4 Correct 367 ms 48208 KB Output is correct
5 Correct 454 ms 48520 KB Output is correct
6 Correct 211 ms 48020 KB Output is correct
7 Correct 358 ms 48212 KB Output is correct
8 Correct 365 ms 48264 KB Output is correct
9 Correct 463 ms 48496 KB Output is correct
10 Correct 186 ms 48016 KB Output is correct
11 Correct 393 ms 48016 KB Output is correct
12 Correct 8 ms 41564 KB Output is correct
13 Correct 1682 ms 193132 KB Output is correct
14 Correct 2416 ms 196952 KB Output is correct
15 Correct 664 ms 212152 KB Output is correct
16 Correct 3248 ms 243036 KB Output is correct
17 Correct 2413 ms 215520 KB Output is correct
18 Correct 1209 ms 95416 KB Output is correct
19 Correct 483 ms 95100 KB Output is correct
20 Correct 1241 ms 98728 KB Output is correct
21 Correct 1103 ms 95892 KB Output is correct
22 Correct 2544 ms 216508 KB Output is correct
23 Correct 2865 ms 217872 KB Output is correct
24 Correct 3732 ms 219296 KB Output is correct
25 Correct 3854 ms 221684 KB Output is correct
26 Correct 3814 ms 219848 KB Output is correct
27 Correct 5242 ms 241460 KB Output is correct
28 Correct 925 ms 218576 KB Output is correct
29 Correct 4033 ms 219408 KB Output is correct
30 Correct 3601 ms 218856 KB Output is correct
31 Correct 3454 ms 219476 KB Output is correct
32 Correct 1191 ms 99476 KB Output is correct
33 Correct 483 ms 95096 KB Output is correct
34 Correct 855 ms 93892 KB Output is correct
35 Correct 836 ms 93900 KB Output is correct
36 Correct 1172 ms 94552 KB Output is correct
37 Correct 1154 ms 94384 KB Output is correct