oj.uz

답안 #780156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780156 2023-07-12T07:02:10 Z adaawf 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 293600 KB 
#include "factories.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
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[]) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    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:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int i = 0; i < g[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int i = 0; i < g[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 38024 KB Output is correct
2 Correct 356 ms 47824 KB Output is correct
3 Correct 354 ms 47692 KB Output is correct
4 Correct 370 ms 47864 KB Output is correct
5 Correct 308 ms 48076 KB Output is correct
6 Correct 409 ms 47896 KB Output is correct
7 Correct 387 ms 47712 KB Output is correct
8 Correct 228 ms 47768 KB Output is correct
9 Correct 323 ms 48036 KB Output is correct
10 Correct 405 ms 47920 KB Output is correct
11 Correct 358 ms 47688 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 37844 KB Output is correct
2 Correct 1287 ms 259016 KB Output is correct
3 Correct 1509 ms 260844 KB Output is correct
4 Correct 1078 ms 261656 KB Output is correct
5 Correct 1527 ms 291584 KB Output is correct
6 Correct 1386 ms 262328 KB Output is correct
7 Correct 1094 ms 90316 KB Output is correct
8 Correct 698 ms 91708 KB Output is correct
9 Correct 757 ms 94984 KB Output is correct
10 Correct 784 ms 91440 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 38024 KB Output is correct
2 Correct 356 ms 47824 KB Output is correct
3 Correct 354 ms 47692 KB Output is correct
4 Correct 370 ms 47864 KB Output is correct
5 Correct 308 ms 48076 KB Output is correct
6 Correct 409 ms 47896 KB Output is correct
7 Correct 387 ms 47712 KB Output is correct
8 Correct 228 ms 47768 KB Output is correct
9 Correct 323 ms 48036 KB Output is correct
10 Correct 405 ms 47920 KB Output is correct
11 Correct 358 ms 47688 KB Output is correct
12 Correct 22 ms 37844 KB Output is correct
13 Correct 1287 ms 259016 KB Output is correct
14 Correct 1509 ms 260844 KB Output is correct
15 Correct 1078 ms 261656 KB Output is correct
16 Correct 1527 ms 291584 KB Output is correct
17 Correct 1386 ms 262328 KB Output is correct
18 Correct 1094 ms 90316 KB Output is correct
19 Correct 698 ms 91708 KB Output is correct
20 Correct 757 ms 94984 KB Output is correct
21 Correct 784 ms 91440 KB Output is correct
22 Correct 1594 ms 267576 KB Output is correct
23 Correct 1722 ms 271256 KB Output is correct
24 Correct 1793 ms 270004 KB Output is correct
25 Correct 1793 ms 271788 KB Output is correct
26 Correct 3138 ms 266940 KB Output is correct
27 Correct 2350 ms 293600 KB Output is correct
28 Correct 1694 ms 283860 KB Output is correct
29 Correct 7188 ms 266492 KB Output is correct
30 Execution timed out 8085 ms 265772 KB Time limit exceeded
31 Halted 0 ms 0 KB -