oj.uz

Submission #1084967

# Submission time Handle Problem Language Result Execution time Memory
1084967 2024-09-07T09:21:20 Z pemguimn Factories (JOI14_factories) C++14
15 / 100
 4017 ms 226896 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;

void Init(int N, int A[], int B[], int D[]){
    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 < min(N, SMALL); i++){
            for(int j = 0; j < min(N, SMALL); j++){
                d[i][j] = w[i] + w[j] - 2 * w[lca(i, j)];
            }
        }
    }
}

const int B = 700;
long long Query(int S, int X[], int T, int Y[]){
    sort(X, X + S), sort(Y, Y + T);
    long long ans = INF;
    if(max(X[S - 1], Y[T - 1]) < 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 30 ms 16720 KB Output is correct
2 Correct 3571 ms 226388 KB Output is correct
3 Correct 3650 ms 226384 KB Output is correct
4 Correct 3744 ms 226448 KB Output is correct
5 Correct 4017 ms 226896 KB Output is correct
6 Correct 2906 ms 226372 KB Output is correct
7 Correct 3717 ms 226236 KB Output is correct
8 Correct 2583 ms 226436 KB Output is correct
9 Correct 4013 ms 226644 KB Output is correct
10 Correct 2988 ms 226388 KB Output is correct
11 Correct 3635 ms 226340 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16468 KB Output is correct
2 Correct 1124 ms 107144 KB Output is correct
3 Correct 2357 ms 108904 KB Output is correct
4 Correct 725 ms 107704 KB Output is correct
5 Correct 1666 ms 138076 KB Output is correct
6 Incorrect 1845 ms 110908 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16720 KB Output is correct
2 Correct 3571 ms 226388 KB Output is correct
3 Correct 3650 ms 226384 KB Output is correct
4 Correct 3744 ms 226448 KB Output is correct
5 Correct 4017 ms 226896 KB Output is correct
6 Correct 2906 ms 226372 KB Output is correct
7 Correct 3717 ms 226236 KB Output is correct
8 Correct 2583 ms 226436 KB Output is correct
9 Correct 4013 ms 226644 KB Output is correct
10 Correct 2988 ms 226388 KB Output is correct
11 Correct 3635 ms 226340 KB Output is correct
12 Correct 20 ms 16468 KB Output is correct
13 Correct 1124 ms 107144 KB Output is correct
14 Correct 2357 ms 108904 KB Output is correct
15 Correct 725 ms 107704 KB Output is correct
16 Correct 1666 ms 138076 KB Output is correct
17 Incorrect 1845 ms 110908 KB Output isn't correct
18 Halted 0 ms 0 KB -