oj.uz

Submission #869243

# Submission time Handle Problem Language Result Execution time Memory
869243 2023-11-03T16:29:58 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4812 ms 324544 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long int f[500005];
int n, d[500005], tin[500005], b[2000005], l[2000005], z = 0;
vector<int> gg[500005], g[500005];
int p[500005][20], pp[2000005][22];
void bfs(int x) {
    queue<int> q;
    q.push(x);
    p[x][0] = x;
    f[x] = d[x] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int j = 1; j <= 19; j++) {
             p[u][j] = p[p[u][j - 1]][j - 1];
             if (p[u][j] == 0) break;
        }
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (d[u] + 1 < d[v]) {
                d[v] = d[u] + 1;
                f[v] = f[u] + gg[u][i];
                p[v][0] = u;
                q.push(v);
            }
        }
    }
}
void dfs(int x, int p) {
    b[++z] = x;
    pp[z][0] = x;
    tin[x] = z;
    for (int w : g[x]) {
        if (w == p) continue;
        dfs(w, x);
        b[++z] = x;
        pp[z][0] = x;
    }
    b[++z] = x;
    pp[z][0] = x;
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < 500000; i++) {
        f[i] = 999999999999999999;
        d[i] = n * 2;
    }
    for (int i = 0; i < n - 1; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(v);
        g[v].push_back(u);
        gg[u].push_back(w);
        gg[v].push_back(w);
    }
    bfs(0);
    dfs(0, -1);
    for (int i = 2; i <= 2000000; i++) l[i] = l[i / 2] + 1;
    for (int i = 1; (1 << i) <= z; i++) {
        for (int j = 1; j <= z - (1 << i) + 1; j++) {
            if (d[pp[j][i - 1]] < d[pp[j + (1 << (i - 1))][i - 1]]) pp[j][i] = pp[j][i - 1];
            else pp[j][i] = pp[j + (1 << (i - 1))][i - 1];
        }
    }
}
int lca(int u, int v) {
    int x = tin[u], y = tin[v];
    if (y <= x) swap(x, y);
    int g = l[y - x + 1];
    int h = pp[x][g], k = pp[y - (1 << g) + 1][g];
    if (d[h] < d[k]) return h;
    return k;
}
long long int check(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}
long long int Query(int S, int X[], int T, int Y[]) {
    if (S > 100 && T > 100) {
        vector<long long int> ff(n, 999999999999999999);
        vector<bool> dda(n, 0), dd(n, 0);
        for (int i = 0; i < T; i++) {
            dda[Y[i]] = 1;
        }
        priority_queue<pair<long long int, long long int>> q;
        for (int i = 0; i < S; i++) {
            q.push({0, X[i]});
            ff[X[i]] = 0;
        }
        while (!q.empty()) {
            int u = q.top().second;
            q.pop();
            if (dd[u] == 1) continue;
            dd[u] = 1;
            if (dda[u] == 1) return ff[u];
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i], w = gg[u][i];
                if (ff[u] + w < ff[v]) {
                    ff[v] = ff[u] + w;
                    q.push({-ff[v], v});
                }
            }
        }
    }
    long long int res = 999999999999999999;
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < T; j++) {
            res = min(res, check(X[i], Y[j]));
        }
    }
    return res;
}

Compilation message

factories.cpp: In function 'void bfs(int)':
factories.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < g[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for (int i = 0; i < g[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 68344 KB Output is correct
2 Correct 347 ms 82112 KB Output is correct
3 Correct 317 ms 82152 KB Output is correct
4 Correct 331 ms 82444 KB Output is correct
5 Correct 323 ms 82572 KB Output is correct
6 Correct 430 ms 82772 KB Output is correct
7 Correct 287 ms 82168 KB Output is correct
8 Correct 281 ms 82308 KB Output is correct
9 Correct 330 ms 82572 KB Output is correct
10 Correct 412 ms 82740 KB Output is correct
11 Correct 299 ms 82296 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68196 KB Output is correct
2 Correct 1098 ms 292296 KB Output is correct
3 Correct 1317 ms 293720 KB Output is correct
4 Correct 822 ms 294448 KB Output is correct
5 Correct 1422 ms 318200 KB Output is correct
6 Correct 1247 ms 294736 KB Output is correct
7 Correct 876 ms 124540 KB Output is correct
8 Correct 653 ms 125396 KB Output is correct
9 Correct 603 ms 127780 KB Output is correct
10 Correct 673 ms 125136 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 68344 KB Output is correct
2 Correct 347 ms 82112 KB Output is correct
3 Correct 317 ms 82152 KB Output is correct
4 Correct 331 ms 82444 KB Output is correct
5 Correct 323 ms 82572 KB Output is correct
6 Correct 430 ms 82772 KB Output is correct
7 Correct 287 ms 82168 KB Output is correct
8 Correct 281 ms 82308 KB Output is correct
9 Correct 330 ms 82572 KB Output is correct
10 Correct 412 ms 82740 KB Output is correct
11 Correct 299 ms 82296 KB Output is correct
12 Correct 12 ms 68196 KB Output is correct
13 Correct 1098 ms 292296 KB Output is correct
14 Correct 1317 ms 293720 KB Output is correct
15 Correct 822 ms 294448 KB Output is correct
16 Correct 1422 ms 318200 KB Output is correct
17 Correct 1247 ms 294736 KB Output is correct
18 Correct 876 ms 124540 KB Output is correct
19 Correct 653 ms 125396 KB Output is correct
20 Correct 603 ms 127780 KB Output is correct
21 Correct 673 ms 125136 KB Output is correct
22 Correct 1504 ms 304148 KB Output is correct
23 Correct 1565 ms 307980 KB Output is correct
24 Correct 1517 ms 305828 KB Output is correct
25 Correct 1593 ms 306808 KB Output is correct
26 Correct 1907 ms 303280 KB Output is correct
27 Correct 1637 ms 324544 KB Output is correct
28 Correct 1527 ms 320232 KB Output is correct
29 Correct 3517 ms 302692 KB Output is correct
30 Correct 4104 ms 302268 KB Output is correct
31 Correct 4812 ms 302788 KB Output is correct
32 Correct 549 ms 129784 KB Output is correct
33 Correct 505 ms 129204 KB Output is correct
34 Correct 532 ms 124012 KB Output is correct
35 Correct 494 ms 124120 KB Output is correct
36 Correct 561 ms 124724 KB Output is correct
37 Correct 639 ms 124508 KB Output is correct