oj.uz

Submission #780195

# Submission time Handle Problem Language Result Execution time Memory
780195 2023-07-12T07:12:46 Z adaawf Factories (JOI14_factories) C++14
33 / 100
 8000 ms 284904 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 (1ll * S * T > 1000000) {
        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 29 ms 37972 KB Output is correct
2 Correct 3869 ms 47692 KB Output is correct
3 Correct 1987 ms 47620 KB Output is correct
4 Correct 1449 ms 47820 KB Output is correct
5 Correct 3616 ms 48076 KB Output is correct
6 Correct 3637 ms 47932 KB Output is correct
7 Correct 2039 ms 47728 KB Output is correct
8 Correct 1707 ms 47752 KB Output is correct
9 Correct 3639 ms 47956 KB Output is correct
10 Correct 3543 ms 47880 KB Output is correct
11 Correct 2074 ms 47744 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37780 KB Output is correct
2 Correct 1221 ms 259048 KB Output is correct
3 Correct 1529 ms 259920 KB Output is correct
4 Correct 1008 ms 261596 KB Output is correct
5 Correct 1702 ms 284904 KB Output is correct
6 Correct 1428 ms 261360 KB Output is correct
7 Correct 1020 ms 90092 KB Output is correct
8 Correct 668 ms 91588 KB Output is correct
9 Correct 589 ms 94056 KB Output is correct
10 Correct 811 ms 91304 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 37972 KB Output is correct
2 Correct 3869 ms 47692 KB Output is correct
3 Correct 1987 ms 47620 KB Output is correct
4 Correct 1449 ms 47820 KB Output is correct
5 Correct 3616 ms 48076 KB Output is correct
6 Correct 3637 ms 47932 KB Output is correct
7 Correct 2039 ms 47728 KB Output is correct
8 Correct 1707 ms 47752 KB Output is correct
9 Correct 3639 ms 47956 KB Output is correct
10 Correct 3543 ms 47880 KB Output is correct
11 Correct 2074 ms 47744 KB Output is correct
12 Correct 19 ms 37780 KB Output is correct
13 Correct 1221 ms 259048 KB Output is correct
14 Correct 1529 ms 259920 KB Output is correct
15 Correct 1008 ms 261596 KB Output is correct
16 Correct 1702 ms 284904 KB Output is correct
17 Correct 1428 ms 261360 KB Output is correct
18 Correct 1020 ms 90092 KB Output is correct
19 Correct 668 ms 91588 KB Output is correct
20 Correct 589 ms 94056 KB Output is correct
21 Correct 811 ms 91304 KB Output is correct
22 Correct 1724 ms 267756 KB Output is correct
23 Correct 2021 ms 271868 KB Output is correct
24 Correct 1873 ms 269452 KB Output is correct
25 Correct 1957 ms 271568 KB Output is correct
26 Execution timed out 8076 ms 262088 KB Time limit exceeded
27 Halted 0 ms 0 KB -