oj.uz

Submission #1082909

# Submission time Handle Problem Language Result Execution time Memory
1082909 2024-09-02T05:13:50 Z pemguimn Factories (JOI14_factories) C++14
18 / 100
 8000 ms 146516 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];
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];
}
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);
}

long long Query(int S, int X[], int T, int Y[]){
    long long ans = INF;
    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;
}

//void local(){
//    int n, q;
//    cin >> n >> q;
//    for(int i = 0; i < n - 1; i++){
//        int x, y, z; cin >> x >> y >> z;
//        adj[x].push_back({y, z}), adj[y].push_back({x, z});
//    }
//    dfs(0, 0);
//    for(int i = 1; i <= q; i++){
//        vector<int> X, Y;
//        int s, t;
//        cin >> s >> t;
//        while(s--) {int x; cin >> x; X.push_back(x);}
//        while(t--) {int x; cin >> x; Y.push_back(x);}
//
//        long long ans = INF;
//        for(int x : X){
//            for(int y : Y){
//                ans = min(ans, w[x] + w[y] - 2LL * w[lca(x, y)]);
//            }
//        }
//        cout << ans << '\n';
//    }
//}
//int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//
//    local();
//    return 0;
//}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 50012 KB Output is correct
2 Execution timed out 8053 ms 53456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43612 KB Output is correct
2 Correct 994 ms 115768 KB Output is correct
3 Correct 2186 ms 118608 KB Output is correct
4 Correct 677 ms 116148 KB Output is correct
5 Correct 1632 ms 146516 KB Output is correct
6 Correct 1739 ms 119376 KB Output is correct
7 Correct 2935 ms 70612 KB Output is correct
8 Correct 639 ms 70840 KB Output is correct
9 Correct 2094 ms 74320 KB Output is correct
10 Correct 1884 ms 71356 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 50012 KB Output is correct
2 Execution timed out 8053 ms 53456 KB Time limit exceeded
3 Halted 0 ms 0 KB -