oj.uz

Submission #926980

# Submission time Handle Problem Language Result Execution time Memory
926980 2024-02-14T06:11:21 Z Aiperiii Factories (JOI14_factories) C++14
0 / 100
 179 ms 33116 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=5e5+5;
vector <pair <ll,ll> > g[N];
ll jmp[N][20];
ll d[N],dis[N],par[N];
void dfs(int v,int p){
    for(auto to : g[v]){
        if(to.ff!=p){
            d[to.ff]=d[v]+1;
            dis[to.ff]=dis[v]+to.ss;
            par[to.ff]=v;
            jmp[to.ff][0]=v;
            dfs(to.ff,v);
        }
    }
}
ll dist(int u,int v){
    ll ans=dis[u]+dis[v];
    if(d[u]<d[v])swap(u,v);
    int lca=0;
    for(int i=19;i>=0;i--){
        if(d[jmp[u][i]]>=d[v]){
            u=jmp[u][i];
        }
    }
    if(u==v)lca=u;
    else{
        for(int i=19;i>=0;i--){
            if(d[jmp[u][i]]!=d[jmp[v][i]]){
                u=jmp[u][i];
                v=jmp[v][i];
            }
        }
        lca=par[u];
    }
    return ans-dis[lca]*2;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;i++){
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs(0,0);
    for(int i=1;i<20;i++){
        for(int j=0;j<N;j++){
            jmp[j][i]=jmp[jmp[j][i-1]][i-1];
        }
    }
}

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

Subtask #1
0 / 15.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

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