oj.uz

Submission #1082918

# Submission time Handle Problem Language Result Execution time Memory
1082918 2024-09-02T05:49:09 Z pemguimn Factories (JOI14_factories) C++17
15 / 100
 8000 ms 226648 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];
}

map<pair<int, int>, long long> mp;
long long c[5005][5005];
void Init(int N, int A[], int B[], int D[]){
    mp.clear();
    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 < N; i++){
        for(int j = 0; j < N; j++){
            c[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;
    for(int i = 0; i < S; i++){
        for(int j = 0; j < T; j++){
            pair<int, int> key = {X[i], Y[j]};
            ans = min(ans, c[X[i]][Y[j]]);
//            if(mp.find(key) != mp.end()){
//                ans = min(ans, mp[key]);
//            } else{
//                mp[key] = w[X[i]] + w[Y[j]] - 2 * w[lca(X[i], Y[j])];
//                ans = min(ans, mp[{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

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:55:28: warning: variable 'key' set but not used [-Wunused-but-set-variable]
   55 |             pair<int, int> key = {X[i], Y[j]};
      |                            ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16728 KB Output is correct
2 Correct 6009 ms 226308 KB Output is correct
3 Correct 3842 ms 226384 KB Output is correct
4 Correct 3933 ms 226196 KB Output is correct
5 Correct 6208 ms 226648 KB Output is correct
6 Correct 5358 ms 226388 KB Output is correct
7 Correct 3632 ms 226284 KB Output is correct
8 Correct 3208 ms 226208 KB Output is correct
9 Correct 6372 ms 226644 KB Output is correct
10 Correct 5567 ms 226324 KB Output is correct
11 Correct 3574 ms 226384 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16308 KB Output is correct
2 Execution timed out 8098 ms 112200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16728 KB Output is correct
2 Correct 6009 ms 226308 KB Output is correct
3 Correct 3842 ms 226384 KB Output is correct
4 Correct 3933 ms 226196 KB Output is correct
5 Correct 6208 ms 226648 KB Output is correct
6 Correct 5358 ms 226388 KB Output is correct
7 Correct 3632 ms 226284 KB Output is correct
8 Correct 3208 ms 226208 KB Output is correct
9 Correct 6372 ms 226644 KB Output is correct
10 Correct 5567 ms 226324 KB Output is correct
11 Correct 3574 ms 226384 KB Output is correct
12 Correct 19 ms 16308 KB Output is correct
13 Execution timed out 8098 ms 112200 KB Time limit exceeded
14 Halted 0 ms 0 KB -