oj.uz

Submission #780192

# Submission time Handle Problem Language Result Execution time Memory
780192 2023-07-12T07:11:28 Z adaawf Factories (JOI14_factories) C++14
33 / 100
 8000 ms 288316 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 > 100000) {
        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 38000 KB Output is correct
2 Correct 414 ms 47820 KB Output is correct
3 Correct 1963 ms 47608 KB Output is correct
4 Correct 343 ms 47824 KB Output is correct
5 Correct 381 ms 47920 KB Output is correct
6 Correct 443 ms 47896 KB Output is correct
7 Correct 1979 ms 47632 KB Output is correct
8 Correct 226 ms 47772 KB Output is correct
9 Correct 369 ms 48000 KB Output is correct
10 Correct 452 ms 47984 KB Output is correct
11 Correct 1996 ms 47740 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37844 KB Output is correct
2 Correct 1183 ms 259060 KB Output is correct
3 Correct 1435 ms 260088 KB Output is correct
4 Correct 956 ms 261680 KB Output is correct
5 Correct 1526 ms 285040 KB Output is correct
6 Correct 1507 ms 261368 KB Output is correct
7 Correct 1156 ms 90176 KB Output is correct
8 Correct 704 ms 91648 KB Output is correct
9 Correct 698 ms 94032 KB Output is correct
10 Correct 704 ms 91220 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38000 KB Output is correct
2 Correct 414 ms 47820 KB Output is correct
3 Correct 1963 ms 47608 KB Output is correct
4 Correct 343 ms 47824 KB Output is correct
5 Correct 381 ms 47920 KB Output is correct
6 Correct 443 ms 47896 KB Output is correct
7 Correct 1979 ms 47632 KB Output is correct
8 Correct 226 ms 47772 KB Output is correct
9 Correct 369 ms 48000 KB Output is correct
10 Correct 452 ms 47984 KB Output is correct
11 Correct 1996 ms 47740 KB Output is correct
12 Correct 20 ms 37844 KB Output is correct
13 Correct 1183 ms 259060 KB Output is correct
14 Correct 1435 ms 260088 KB Output is correct
15 Correct 956 ms 261680 KB Output is correct
16 Correct 1526 ms 285040 KB Output is correct
17 Correct 1507 ms 261368 KB Output is correct
18 Correct 1156 ms 90176 KB Output is correct
19 Correct 704 ms 91648 KB Output is correct
20 Correct 698 ms 94032 KB Output is correct
21 Correct 704 ms 91220 KB Output is correct
22 Correct 1480 ms 267608 KB Output is correct
23 Correct 1579 ms 271220 KB Output is correct
24 Correct 1677 ms 269368 KB Output is correct
25 Correct 1625 ms 270972 KB Output is correct
26 Correct 1920 ms 266152 KB Output is correct
27 Correct 1770 ms 288316 KB Output is correct
28 Correct 1652 ms 283776 KB Output is correct
29 Correct 3638 ms 265804 KB Output is correct
30 Execution timed out 8061 ms 261212 KB Time limit exceeded
31 Halted 0 ms 0 KB -