oj.uz

Submission #780160

# Submission time Handle Problem Language Result Execution time Memory
780160 2023-07-12T07:03:36 Z adaawf Factories (JOI14_factories) C++17
33 / 100
 8000 ms 288304 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 > 45 && T > 45) {
        vector<long long int> ff(n);
        vector<bool> dda(n), dd(n);
        for (int i = 0; i < n; i++) {
            dd[i] = dda[i] = 0;
            ff[i] = 999999999999999999;
        }
        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:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (int i = 0; i < g[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37972 KB Output is correct
2 Correct 307 ms 47692 KB Output is correct
3 Correct 355 ms 47664 KB Output is correct
4 Correct 313 ms 47820 KB Output is correct
5 Correct 308 ms 47992 KB Output is correct
6 Correct 400 ms 48336 KB Output is correct
7 Correct 358 ms 47624 KB Output is correct
8 Correct 206 ms 47756 KB Output is correct
9 Correct 305 ms 47984 KB Output is correct
10 Correct 430 ms 47880 KB Output is correct
11 Correct 345 ms 47708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37744 KB Output is correct
2 Correct 1192 ms 259040 KB Output is correct
3 Correct 1424 ms 259892 KB Output is correct
4 Correct 951 ms 261568 KB Output is correct
5 Correct 1515 ms 284876 KB Output is correct
6 Correct 1458 ms 261324 KB Output is correct
7 Correct 977 ms 90052 KB Output is correct
8 Correct 687 ms 91648 KB Output is correct
9 Correct 545 ms 93944 KB Output is correct
10 Correct 734 ms 91280 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37972 KB Output is correct
2 Correct 307 ms 47692 KB Output is correct
3 Correct 355 ms 47664 KB Output is correct
4 Correct 313 ms 47820 KB Output is correct
5 Correct 308 ms 47992 KB Output is correct
6 Correct 400 ms 48336 KB Output is correct
7 Correct 358 ms 47624 KB Output is correct
8 Correct 206 ms 47756 KB Output is correct
9 Correct 305 ms 47984 KB Output is correct
10 Correct 430 ms 47880 KB Output is correct
11 Correct 345 ms 47708 KB Output is correct
12 Correct 20 ms 37744 KB Output is correct
13 Correct 1192 ms 259040 KB Output is correct
14 Correct 1424 ms 259892 KB Output is correct
15 Correct 951 ms 261568 KB Output is correct
16 Correct 1515 ms 284876 KB Output is correct
17 Correct 1458 ms 261324 KB Output is correct
18 Correct 977 ms 90052 KB Output is correct
19 Correct 687 ms 91648 KB Output is correct
20 Correct 545 ms 93944 KB Output is correct
21 Correct 734 ms 91280 KB Output is correct
22 Correct 1592 ms 267612 KB Output is correct
23 Correct 1661 ms 271200 KB Output is correct
24 Correct 1600 ms 269332 KB Output is correct
25 Correct 1630 ms 271088 KB Output is correct
26 Correct 3131 ms 266128 KB Output is correct
27 Correct 1908 ms 288304 KB Output is correct
28 Correct 1710 ms 283828 KB Output is correct
29 Correct 6827 ms 265820 KB Output is correct
30 Execution timed out 8099 ms 265220 KB Time limit exceeded
31 Halted 0 ms 0 KB -