oj.uz

Submission #780207

# Submission time Handle Problem Language Result Execution time Memory
780207 2023-07-12T07:15:43 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 5376 ms 288284 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 31 ms 37972 KB Output is correct
2 Correct 349 ms 47700 KB Output is correct
3 Correct 341 ms 47664 KB Output is correct
4 Correct 362 ms 47808 KB Output is correct
5 Correct 351 ms 47952 KB Output is correct
6 Correct 524 ms 48292 KB Output is correct
7 Correct 310 ms 47684 KB Output is correct
8 Correct 316 ms 47788 KB Output is correct
9 Correct 357 ms 47964 KB Output is correct
10 Correct 449 ms 47872 KB Output is correct
11 Correct 296 ms 47676 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37788 KB Output is correct
2 Correct 1289 ms 259012 KB Output is correct
3 Correct 1513 ms 260040 KB Output is correct
4 Correct 968 ms 261704 KB Output is correct
5 Correct 1529 ms 284796 KB Output is correct
6 Correct 1425 ms 261364 KB Output is correct
7 Correct 1064 ms 90040 KB Output is correct
8 Correct 682 ms 91736 KB Output is correct
9 Correct 738 ms 94036 KB Output is correct
10 Correct 731 ms 91316 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 37972 KB Output is correct
2 Correct 349 ms 47700 KB Output is correct
3 Correct 341 ms 47664 KB Output is correct
4 Correct 362 ms 47808 KB Output is correct
5 Correct 351 ms 47952 KB Output is correct
6 Correct 524 ms 48292 KB Output is correct
7 Correct 310 ms 47684 KB Output is correct
8 Correct 316 ms 47788 KB Output is correct
9 Correct 357 ms 47964 KB Output is correct
10 Correct 449 ms 47872 KB Output is correct
11 Correct 296 ms 47676 KB Output is correct
12 Correct 17 ms 37788 KB Output is correct
13 Correct 1289 ms 259012 KB Output is correct
14 Correct 1513 ms 260040 KB Output is correct
15 Correct 968 ms 261704 KB Output is correct
16 Correct 1529 ms 284796 KB Output is correct
17 Correct 1425 ms 261364 KB Output is correct
18 Correct 1064 ms 90040 KB Output is correct
19 Correct 682 ms 91736 KB Output is correct
20 Correct 738 ms 94036 KB Output is correct
21 Correct 731 ms 91316 KB Output is correct
22 Correct 1590 ms 267572 KB Output is correct
23 Correct 1762 ms 271144 KB Output is correct
24 Correct 1696 ms 269280 KB Output is correct
25 Correct 1831 ms 270980 KB Output is correct
26 Correct 2007 ms 266156 KB Output is correct
27 Correct 1753 ms 288284 KB Output is correct
28 Correct 1724 ms 283748 KB Output is correct
29 Correct 3744 ms 265784 KB Output is correct
30 Correct 4471 ms 265264 KB Output is correct
31 Correct 5376 ms 265852 KB Output is correct
32 Correct 670 ms 95984 KB Output is correct
33 Correct 635 ms 94492 KB Output is correct
34 Correct 584 ms 89216 KB Output is correct
35 Correct 700 ms 89228 KB Output is correct
36 Correct 880 ms 89572 KB Output is correct
37 Correct 734 ms 89548 KB Output is correct