oj.uz

Submission #1084974

# Submission time Handle Problem Language Result Execution time Memory
1084974 2024-09-07T09:28:03 Z pemguimn Factories (JOI14_factories) C++14
33 / 100
 8000 ms 217232 KB 
#include <bits/stdc++.h>
//#include "factories.h"
using namespace std;

const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, int>> adj[maxN];

int h[maxN], par[LOG][maxN];

const int SMALL = 5e3 + 5;
long long d[SMALL][SMALL];
long long w[maxN];
void dfs(int i, int pre){
    for(pair<int, int> e : adj[i]){
        int x = e.first, c = e.second;
        if(x == pre) continue;
        h[x] = h[i] + 1, w[x] = w[i] + c;
        par[0][x] = i;
        for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
}

int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for(int i = 0; i < LOG; i++){
        if(d & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = LOG - 1; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}

map<pair<int, int>, long long> mp;

int sz = 0;
void Init(int N, int A[], int B[], int D[]){
    sz = N;
    for(int i = 0; i < N - 1; i++){
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    if(N < SMALL){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d[i][j] = w[i] + w[j] - 2 * w[lca(i, j)];
            }
        }
    }
}

long long Query(int S, int X[], int T, int Y[]){
    long long ans = INF;
    if(sz < SMALL){
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++){
                ans = min(ans, d[X[i]][Y[j]]);
            }
        }
    } else{
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++){
                ans = min(ans, w[X[i]] + w[Y[j]] - 2 * w[lca(X[i], Y[j])]);
            }
        }
    }
    return ans;
}

#ifdef LOCAL
const int MAX = 1e3 + 5;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    int x[MAX], y[MAX], d[MAX];
    for(int i = 0; i < n - 1; i++){
        cin >> x[i] >> y[i] >> d[i];
    }
    Init(n, x, y, d);
    for(int i = 1; i <= q; i++){
        int s, t; cin >> s >> t;
        int a[MAX], b[MAX];
        for(int i = 0; i < s; i++) cin >> a[i];
        for(int i = 0; i < t; i++) cin >> b[i];
        cout << Query(s, a, t, b) << '\n';
    }
    return 0;
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16472 KB Output is correct
2 Correct 5926 ms 216856 KB Output is correct
3 Correct 3654 ms 216948 KB Output is correct
4 Correct 4045 ms 216752 KB Output is correct
5 Correct 6681 ms 217168 KB Output is correct
6 Correct 5493 ms 216740 KB Output is correct
7 Correct 3561 ms 216872 KB Output is correct
8 Correct 3096 ms 216920 KB Output is correct
9 Correct 6518 ms 217232 KB Output is correct
10 Correct 5576 ms 216916 KB Output is correct
11 Correct 3659 ms 216908 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16388 KB Output is correct
2 Correct 1208 ms 88696 KB Output is correct
3 Correct 2768 ms 91140 KB Output is correct
4 Correct 738 ms 89284 KB Output is correct
5 Correct 1768 ms 119504 KB Output is correct
6 Correct 2015 ms 92284 KB Output is correct
7 Correct 3225 ms 49944 KB Output is correct
8 Correct 686 ms 50492 KB Output is correct
9 Correct 2308 ms 54316 KB Output is correct
10 Correct 1994 ms 51228 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16472 KB Output is correct
2 Correct 5926 ms 216856 KB Output is correct
3 Correct 3654 ms 216948 KB Output is correct
4 Correct 4045 ms 216752 KB Output is correct
5 Correct 6681 ms 217168 KB Output is correct
6 Correct 5493 ms 216740 KB Output is correct
7 Correct 3561 ms 216872 KB Output is correct
8 Correct 3096 ms 216920 KB Output is correct
9 Correct 6518 ms 217232 KB Output is correct
10 Correct 5576 ms 216916 KB Output is correct
11 Correct 3659 ms 216908 KB Output is correct
12 Correct 20 ms 16388 KB Output is correct
13 Correct 1208 ms 88696 KB Output is correct
14 Correct 2768 ms 91140 KB Output is correct
15 Correct 738 ms 89284 KB Output is correct
16 Correct 1768 ms 119504 KB Output is correct
17 Correct 2015 ms 92284 KB Output is correct
18 Correct 3225 ms 49944 KB Output is correct
19 Correct 686 ms 50492 KB Output is correct
20 Correct 2308 ms 54316 KB Output is correct
21 Correct 1994 ms 51228 KB Output is correct
22 Execution timed out 8035 ms 113992 KB Time limit exceeded
23 Halted 0 ms 0 KB -