oj.uz

Submission #1084971

# Submission time Handle Problem Language Result Execution time Memory
1084971 2024-09-07T09:25:40 Z pemguimn Factories (JOI14_factories) C++14
15 / 100
 8000 ms 286532 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);
    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)];
        }
    }
}

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 25 ms 16476 KB Output is correct
2 Correct 3340 ms 216924 KB Output is correct
3 Correct 3686 ms 216800 KB Output is correct
4 Correct 3674 ms 216912 KB Output is correct
5 Correct 3943 ms 217172 KB Output is correct
6 Correct 2886 ms 216916 KB Output is correct
7 Correct 3674 ms 216816 KB Output is correct
8 Correct 2584 ms 216820 KB Output is correct
9 Correct 3985 ms 217172 KB Output is correct
10 Correct 2969 ms 216728 KB Output is correct
11 Correct 3751 ms 216916 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16472 KB Output is correct
2 Correct 3689 ms 284536 KB Output is correct
3 Execution timed out 8055 ms 286532 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16476 KB Output is correct
2 Correct 3340 ms 216924 KB Output is correct
3 Correct 3686 ms 216800 KB Output is correct
4 Correct 3674 ms 216912 KB Output is correct
5 Correct 3943 ms 217172 KB Output is correct
6 Correct 2886 ms 216916 KB Output is correct
7 Correct 3674 ms 216816 KB Output is correct
8 Correct 2584 ms 216820 KB Output is correct
9 Correct 3985 ms 217172 KB Output is correct
10 Correct 2969 ms 216728 KB Output is correct
11 Correct 3751 ms 216916 KB Output is correct
12 Correct 19 ms 16472 KB Output is correct
13 Correct 3689 ms 284536 KB Output is correct
14 Execution timed out 8055 ms 286532 KB Time limit exceeded
15 Halted 0 ms 0 KB -