oj.uz

Submission #978538

# Submission time Handle Problem Language Result Execution time Memory
978538 2024-05-09T10:13:24 Z tnknguyen_ Factories (JOI14_factories) C++14
0 / 100
 111 ms 105296 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define pii pair<int, int>
//#define int long long 

const int MX = 5e5 + 5;
const int LG = 19;
vector<pii> gr[MX];
int up[LG][MX], f[LG][MX], dep[MX];
int n, q;

void dfs(int u, int p)  {
    dep[u] = dep[p] + 1, up[0][u] = p;
    for(int j=1; j<LG; ++j){
        up[j][u] = up[j-1][up[j-1][u]];
        f[j][u] = f[j-1][u] + f[j-1][up[j-1][u]];
    }

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p){
            f[0][v] = c;
            dfs(v, u);
        }
    }
}

ll dist(int u, int v){
    if(dep[u] < dep[v]) { swap(u, v); }

    ll ans = 0;
    for(int j=LG-1; j>=0; --j){
        if(dep[up[j][u]] >= dep[v]){
            ans += f[j][u];
            u = up[j][u];
        }
    }

    if(u == v) { return ans; }

    for(int j=LG-1; j>=0; --j){
        if(up[j][u] != up[j][v]){
            ans += f[j][u] + f[j][v];
            u = up[j][u], v = up[j][v];
        }
    }
    return ans + f[0][u] + f[0][v];
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n; ++i){
        int u = A[i], v = B[i], c = D[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    dfs(1, 1);
}

ll Query(int S, int X[], int T, int Y[]){
    ll ans = 1e18;
    for(int i=0; i<S; ++i){
        for(int j=0; j<T; ++j){
            ans = min(ans, dist(X[i], Y[j]));
        }
    }
    return ans;
}

// int32_t main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     freopen("main.inp","r",stdin);
//     freopen("main.out","w",stdout);

//     cin>>n>>q;
//     for(int i=1; i<n; ++i){
//         int u, v, c;
//         cin>>u>>v>>c;
//         u++, v++;
//         gr[u].push_back({v, c});
//         gr[v].push_back({u, c});
//     }

//     dfs(1, 0);

//     while(q--){
//         int x, y;
//         cin>>x>>y;

//         vector<int> a(x), b(y);
//         for(int i=0; i<x; ++i) { 
//             cin>>a[i]; 
//             ++a[i];
//         }
//         for(int i=0; i<y; ++i) { 
//             cin>>b[i]; 
//             ++b[i];
//         }

//         ll ans = 1e18;
//         for(int i=0; i<x; ++i){
//             for(int j=0; j<y; ++j){
//                 ans = min(ans, dist(a[i], b[j]));
//             }
//         }
//         cout<<ans<<"\n";
//     }

//     return 0;
// }

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 105296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 105052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 105296 KB Output isn't correct
2 Halted 0 ms 0 KB -