oj.uz

Submission #969548

# Submission time Handle Problem Language Result Execution time Memory
969548 2024-04-25T09:50:49 Z Turkhuu Factories (JOI14_factories) C++17
100 / 100
 4882 ms 224360 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 < 19 && 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 13 ms 41560 KB Output is correct
2 Correct 295 ms 48012 KB Output is correct
3 Correct 411 ms 48012 KB Output is correct
4 Correct 397 ms 48260 KB Output is correct
5 Correct 458 ms 48504 KB Output is correct
6 Correct 185 ms 48208 KB Output is correct
7 Correct 385 ms 48268 KB Output is correct
8 Correct 402 ms 48228 KB Output is correct
9 Correct 468 ms 48524 KB Output is correct
10 Correct 211 ms 48012 KB Output is correct
11 Correct 422 ms 48212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 41564 KB Output is correct
2 Correct 2024 ms 193072 KB Output is correct
3 Correct 2437 ms 196836 KB Output is correct
4 Correct 702 ms 193796 KB Output is correct
5 Correct 3580 ms 224360 KB Output is correct
6 Correct 2622 ms 196828 KB Output is correct
7 Correct 909 ms 81352 KB Output is correct
8 Correct 446 ms 81264 KB Output is correct
9 Correct 1256 ms 84708 KB Output is correct
10 Correct 1296 ms 81876 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41560 KB Output is correct
2 Correct 295 ms 48012 KB Output is correct
3 Correct 411 ms 48012 KB Output is correct
4 Correct 397 ms 48260 KB Output is correct
5 Correct 458 ms 48504 KB Output is correct
6 Correct 185 ms 48208 KB Output is correct
7 Correct 385 ms 48268 KB Output is correct
8 Correct 402 ms 48228 KB Output is correct
9 Correct 468 ms 48524 KB Output is correct
10 Correct 211 ms 48012 KB Output is correct
11 Correct 422 ms 48212 KB Output is correct
12 Correct 16 ms 41564 KB Output is correct
13 Correct 2024 ms 193072 KB Output is correct
14 Correct 2437 ms 196836 KB Output is correct
15 Correct 702 ms 193796 KB Output is correct
16 Correct 3580 ms 224360 KB Output is correct
17 Correct 2622 ms 196828 KB Output is correct
18 Correct 909 ms 81352 KB Output is correct
19 Correct 446 ms 81264 KB Output is correct
20 Correct 1256 ms 84708 KB Output is correct
21 Correct 1296 ms 81876 KB Output is correct
22 Correct 2902 ms 192364 KB Output is correct
23 Correct 2699 ms 193416 KB Output is correct
24 Correct 3829 ms 195088 KB Output is correct
25 Correct 3956 ms 197316 KB Output is correct
26 Correct 3736 ms 195636 KB Output is correct
27 Correct 4882 ms 216876 KB Output is correct
28 Correct 919 ms 193892 KB Output is correct
29 Correct 3181 ms 195424 KB Output is correct
30 Correct 3193 ms 194532 KB Output is correct
31 Correct 3274 ms 195304 KB Output is correct
32 Correct 1109 ms 85560 KB Output is correct
33 Correct 360 ms 81664 KB Output is correct
34 Correct 739 ms 80372 KB Output is correct
35 Correct 786 ms 80400 KB Output is correct
36 Correct 1006 ms 80852 KB Output is correct
37 Correct 990 ms 80840 KB Output is correct