Submission #926978

#	Time	Username	Problem	Language	Result	Execution time	Memory
926978		Aiperiii	Factories (JOI14_factories)	C++14	0 / 100	178 ms	33368 KiB

factories

#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);
        }
    }
}
int 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[]) {
    int 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;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:59:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   59 |     int mn=1e18;
      |            ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67