oj.uz

Submission #978539

# Submission time Handle Problem Language Result Execution time Memory
978539 2024-05-09T10:14:47 Z tnknguyen_ Factories (JOI14_factories) C++14
0 / 100
 8000 ms 149212 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]+1, Y[j]+1));
        }
    }
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 105052 KB Output is correct
2 Execution timed out 8032 ms 116820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 105052 KB Output is correct
2 Incorrect 1970 ms 149212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 105052 KB Output is correct
2 Execution timed out 8032 ms 116820 KB Time limit exceeded
3 Halted 0 ms 0 KB -