oj.uz

답안 #780202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780202 2023-07-12T07:14:39 Z adaawf 공장들 (JOI14_factories) C++14
100 / 100
 5526 ms 288984 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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 38128 KB Output is correct
2 Correct 356 ms 48284 KB Output is correct
3 Correct 304 ms 48204 KB Output is correct
4 Correct 354 ms 48336 KB Output is correct
5 Correct 339 ms 48456 KB Output is correct
6 Correct 438 ms 48388 KB Output is correct
7 Correct 330 ms 48204 KB Output is correct
8 Correct 302 ms 48328 KB Output is correct
9 Correct 355 ms 48688 KB Output is correct
10 Correct 444 ms 48624 KB Output is correct
11 Correct 336 ms 48312 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 37768 KB Output is correct
2 Correct 1238 ms 259144 KB Output is correct
3 Correct 1463 ms 260016 KB Output is correct
4 Correct 957 ms 261748 KB Output is correct
5 Correct 1621 ms 284984 KB Output is correct
6 Correct 1481 ms 261464 KB Output is correct
7 Correct 1121 ms 90696 KB Output is correct
8 Correct 754 ms 92336 KB Output is correct
9 Correct 742 ms 94596 KB Output is correct
10 Correct 871 ms 91860 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 38128 KB Output is correct
2 Correct 356 ms 48284 KB Output is correct
3 Correct 304 ms 48204 KB Output is correct
4 Correct 354 ms 48336 KB Output is correct
5 Correct 339 ms 48456 KB Output is correct
6 Correct 438 ms 48388 KB Output is correct
7 Correct 330 ms 48204 KB Output is correct
8 Correct 302 ms 48328 KB Output is correct
9 Correct 355 ms 48688 KB Output is correct
10 Correct 444 ms 48624 KB Output is correct
11 Correct 336 ms 48312 KB Output is correct
12 Correct 18 ms 37768 KB Output is correct
13 Correct 1238 ms 259144 KB Output is correct
14 Correct 1463 ms 260016 KB Output is correct
15 Correct 957 ms 261748 KB Output is correct
16 Correct 1621 ms 284984 KB Output is correct
17 Correct 1481 ms 261464 KB Output is correct
18 Correct 1121 ms 90696 KB Output is correct
19 Correct 754 ms 92336 KB Output is correct
20 Correct 742 ms 94596 KB Output is correct
21 Correct 871 ms 91860 KB Output is correct
22 Correct 1755 ms 267644 KB Output is correct
23 Correct 1859 ms 271224 KB Output is correct
24 Correct 1707 ms 269292 KB Output is correct
25 Correct 1719 ms 270868 KB Output is correct
26 Correct 1975 ms 266124 KB Output is correct
27 Correct 1835 ms 288984 KB Output is correct
28 Correct 1669 ms 284320 KB Output is correct
29 Correct 3678 ms 265920 KB Output is correct
30 Correct 4456 ms 265368 KB Output is correct
31 Correct 5526 ms 265980 KB Output is correct
32 Correct 527 ms 96488 KB Output is correct
33 Correct 612 ms 94980 KB Output is correct
34 Correct 573 ms 89676 KB Output is correct
35 Correct 608 ms 89892 KB Output is correct
36 Correct 700 ms 90072 KB Output is correct
37 Correct 633 ms 90208 KB Output is correct