oj.uz

Submission #780184

# Submission time Handle Problem Language Result Execution time Memory
780184 2023-07-12T07:09:50 Z adaawf Factories (JOI14_factories) C++17
15 / 100
 8000 ms 284956 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 > 10 && T > 10) {
        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 25 ms 37972 KB Output is correct
2 Correct 318 ms 47696 KB Output is correct
3 Correct 310 ms 47612 KB Output is correct
4 Correct 300 ms 47840 KB Output is correct
5 Correct 363 ms 47948 KB Output is correct
6 Correct 412 ms 47872 KB Output is correct
7 Correct 320 ms 47664 KB Output is correct
8 Correct 191 ms 47672 KB Output is correct
9 Correct 291 ms 47956 KB Output is correct
10 Correct 397 ms 47912 KB Output is correct
11 Correct 313 ms 47668 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37744 KB Output is correct
2 Correct 1319 ms 259068 KB Output is correct
3 Correct 1560 ms 259908 KB Output is correct
4 Correct 1074 ms 261544 KB Output is correct
5 Correct 1583 ms 284956 KB Output is correct
6 Correct 1556 ms 261340 KB Output is correct
7 Execution timed out 8082 ms 90008 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37972 KB Output is correct
2 Correct 318 ms 47696 KB Output is correct
3 Correct 310 ms 47612 KB Output is correct
4 Correct 300 ms 47840 KB Output is correct
5 Correct 363 ms 47948 KB Output is correct
6 Correct 412 ms 47872 KB Output is correct
7 Correct 320 ms 47664 KB Output is correct
8 Correct 191 ms 47672 KB Output is correct
9 Correct 291 ms 47956 KB Output is correct
10 Correct 397 ms 47912 KB Output is correct
11 Correct 313 ms 47668 KB Output is correct
12 Correct 23 ms 37744 KB Output is correct
13 Correct 1319 ms 259068 KB Output is correct
14 Correct 1560 ms 259908 KB Output is correct
15 Correct 1074 ms 261544 KB Output is correct
16 Correct 1583 ms 284956 KB Output is correct
17 Correct 1556 ms 261340 KB Output is correct
18 Execution timed out 8082 ms 90008 KB Time limit exceeded
19 Halted 0 ms 0 KB -